|
#include<stdio.h>
#include<string.h>
const int size=100001;
// 1<= n <= 100,000, 0 < m <= 200,000
int d[size],p[size],f[size],an[size],nbs[size];
int ev[size*2],ew[size*2],next[size*2];
int n,e;
inline int min(int a,int b)
{
return a<b?a:b;
}
void find_path(int st,int en)
{
int i,k,m,pos,temp;
//初始化
memset(d,0,sizeof(d));
memset(p,0,sizeof(p));
memset(f,0,sizeof(f));
for(i=nbs[st];i;i=next[i])
{d[ev[i]]=ew[i];p[ev[i]]=st;}
f[st]=1;
for(k=1;k<n;k++)
{
m=0;
pos=0;
for(i=1;i<=n;i++)
if(f[i]==0&&d[i]>m) {m=d[i];pos=i;}
if(pos==0)break;
f[pos]=1;
for(i=nbs[pos];i;i=next[i])
{
temp=min(m,ew[i]);
if(temp>d[ev[i]])
{d[ev[i]]=temp;p[ev[i]]=pos;}
}
}
}
int main()
{
int i,num,u,v,w,temp,k;
while(scanf("%d%d",&n,&e)!=EOF)
{
num=0;
for(i=1;i<=n;i++) nbs[i]=0;
while(e--)
{
scanf("%d%d%d",&u,&v,&w);
next[++num]=nbs[u];nbs[u]=num;
ev[num]=v;ew[num]=w;
}
// for(i=nbs[1];i!=0;i=next[i])
// printf("%d %d\n",i,ev[i]);
//d[1][n]
find_path(1,n);
if(d[n]==0)
{printf("-1\n");continue;}
temp=n;an[1]=temp;k=1;
while(p[temp])
{
an[++k]=p[temp];
temp=p[temp];
}
for(i=k;i>1;i--)
printf("%d ",an[i]);
printf("%d\n",an[1]);
}
return 0;
}
/*
7 9
1 2 10
1 3 1
3 4 4
2 4 6
2 6 12
6 7 3
5 7 8
4 5 9
4 7 9
7 6
1 2 10
1 3 1
3 4 4
2 4 6
2 6 12
4 5 9
2 0
1 0
*/
|
