#include

using namespace std;

struct node{

long go,cos;

node *next;

};

long n,m,i,x,y,z,f,t,l[100000],w[200][200],d[200],hash[200],ed[200];

bool h[200];

node *a[200],*p,*q;

bool relax(long a,long b,long c)

{

if (d[a]+c>d) {d=d[a]+c; hash=1; w[1]=a; return true;}

else

{

if (d[a]+c==d) {hash++; w[hash]=a;}

return false;

}

}

void dfs(long now)

{

ed[now]=true;

for (i=1; inext=NULL;}

else

{p=a[x];

while (p->next!=NULL && p->next->gonext;

q=new node; q->go=y; q->cos=z; q->next=p->next;

p->next=q;}

}

n++;

d[1]=0; for (i=2; igo]))

{t++; l[t]=p->go; h[p->go]=true;}

p=p->next;

}

h[l[f]]=false;

f++;

}

printf("%d\n",d[n]);

memset(ed,false,sizeof(ed));

print();

}