#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
const int inf=(1<<29);
typedef pair<int,int> pereche;
const int maxn=1000;
void citire(vector< pereche >G[],int &n,int &m)
{
    ifstream fin("graf.in");
    fin>>n>>m;
    int x,y,c;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
}
void drum(int n,int T[100])
{
    if(!n) return;
    drum(T[n],T);
    cout<<n<<" ";
}
void dijkstra(vector<pereche> G[],int n,int D[],int T[])
{
    bool viz[100];
    for(int i=0; i<=n; i++)
    {
        D[i]=inf;
        T[i]=0;
        viz[i]=false;
    }
    D[1]=0;
    viz[1]=true;

    vector<pereche>::iterator it;

    for(it=G[1].begin(); it!=G[1].end(); it++)
        D[it->first]=it->second;

   /// alg dijkstra

    for(int i=1; i<=n; i++)
    {
        int min=0;

        //gasim nodul min cu D[min] minim
        for(int j=1; j<=n; ++j)
            if(!viz[j]&&D[j]<D[min])
                min=j;
        viz[min]=true;

        //relaxam vecinii lui min


        for(j=G[min].begin(); j!=G[min].end(); j++)
            if(D[min]+j->second<D[j->first])
            {
                D[j->first]=D[min]+j->second;
                T[j->first]=min;
            }
    }
}

int main()
{
    int n,m,D[100],T[100];
    vector<pereche> G[100];
    citire(G,n,m);
    dijkstra(G,n,D,T);
    for(int i=1;i<=n;i++)
    cout<<D[i]<<" ";
    //drumul
    drum(n,T);
    return 0;
}