#include<iostream>
using namespace std;
#include<cstring>
#define maxSize 100
#define INF 0x3f3f3f3f
typedef struct
{
int no; //顶点编号
char info; //顶点其他信息
}VertexType;
typedef struct
{
int edges[maxSize][maxSize];
int n,e; //分别为顶点数和边数
VertexType vex[maxSize]; //存放结点信息
}MGraph;
void printfPath(int path[],int a)
{
int stack[maxSize],top=-1;
while(path[a]!=-1)
{
stack[++top]=a;
a=path[a];
}
stack[++top]=a;
while(top!=-1)
cout<<stack[top--]<<" ";
cout<<endl;
}
void Dijkstra(MGraph g,int v,int dist[],int path[])
{
int set[maxSize];
int min,i,j,u;
for(i=0;i<g.n;++i)
{
dist[i]=g.edges[v][i];
set[i]=0;
if(g.edges[v][i]<INF)
path[i]=v;
else
path[i]=-1;
}
set[v]=1;path[v]=-1;
for(i=0;i<g.n-1;++i)
{
min=INF;
for(j=0;j<g.n;++j)
if(set[j]==0&&dist[j]<min)
{
u=j;
min=dist[j];
}
set[u]=1;
for(j=0;j<g.n;++j)
{
if(set[j]==0&&dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
}
}
/*
7 12
0 1 4 0 2 6 0 3 6 1 4 7
1 2 1 3 2 2 2 4 6 3 5 5
2 5 4 5 4 1 4 6 6 5 6 8
*/
int main()
{
MGraph g;
int n,e,sum;
cin>>n>>e;
g.n=n,g.e=e;
memset(g.edges,INF,sizeof(g.edges));
for(int i=0;i<g.e;++i)
{
int a,b,w;
cin>>a>>b>>w;
g.edges[i][i]=0;
g.edges[a][b]=w;
}
int dist[maxSize],path[maxSize];
Dijkstra(g,0,dist,path);
for(int i=0;i<n;++i)
cout<<dist[i]<<" ";
cout<<endl;
printfPath(path,6);
}
