#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iomanip>

#include<algorithm>

using namespace std;

#define inf 1<<29

#define nu 10005

#define maxnum 100000

int n,m;

int c[nu][nu];

int dist[nu];

int pre[nu];

int book[nu];

void dijkstra(int n,int v){

  int i,j;

  memset(book,,sizeof(book));

  for(i=;i<=n;i++){

    dist[i]=c[v][i];

    if(dist[i]>maxnum) pre[i]=;

    else pre[i]=v;

  }

  dist[v]=;

  book[v]=;

  for(i=;i<n;i++){

    int temp=maxnum;

    int u=v;

    for(j=;j<=n;j++){

        if(!book[j]&&dist[j]<temp)

            u=j,temp=dist[j];

    }

    book[u]=;

    for(j=;j<=n;j++){

        if(!book[j]&&c[u][j]<maxnum)

        {

            if(dist[j]>dist[u]+c[u][j]){

                dist[j]=dist[u]+c[u][j];

             pre[j]=u;

            }

        }

    }

  }

   for(int i=;i<=n;i++)

    cout<<dist[i]<<endl;

}

void traceback(int v,int i,int pre[])

{

    cout<<i<<" <--";

    i=pre[i];

    if(i!=v) traceback(v,i,pre);

    if(i==v) cout<<i<<endl;

}

int main()

{

    cin>>n>>m;

    for(int i=;i<nu;i++)

        for(int j=;j<nu;j++)

        if(i!=j)

           c[i][j]=c[j][i]=maxnum;

    else

        c[i][j]=;

    for(int i=;i<=m;i++){

        int x,y,z;

        cin>>x>>y>>z;

        c[x][y]=c[y][x]=z;

    }

    dijkstra(n,);

    traceback(,,pre);

    return ;

}