#include <iostream>
#include <fstream>
#define INF 1000000000
using namespace std;
int a[102][102],v[102],d[102],t[102],n,x,i,m,o,p;
void citire()
{
    int i,j,c;
    ifstream fin("graf.in");
    fin>>n>>m;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
            if(i==j) a[i][j]=0;
            else a[i][j]=INF;
    }
    for(int i=1; i<=m; i++)
    {
        fin>>o>>p>>c;
        a[o][p]=c;
    }
    fin.close();
}
void dijkstra(int x)
{
    int i,j,mi,ok=1,k;
    for(i=1; i<=n; i++)
    {
        d[i]=a[x][i];
        if((d[i]<INF) && (d[i]>0))
            t[i]=x;
    }
    v[x]=1;
    t[x]=0;
    while(ok)
    {
        mi=INF;
        for(i=1; i<=n; i++) ///cautam cel mai apropiat nod de x
            if((v[i]==0) && (mi>d[i]))
            {
                mi=d[i];
                k=i;
            }
        if(mi==INF)ok=0;
        else
        {
            v[k]=1;///marcam nodulca fiind verificat
            ///parcurgem nodurile adiacente si actualizam vectorul d si t
            for(i=1; i<=n; i++)
                if((v[i]==0) && (d[i]>d[k]+a[k][i]) )
                {
                    d[i]=d[k]+a[k][i];
                    t[i]=k;

                }
        }

    }
}
void afis(int x)
{
    if(x!=0)
    {
        afis(t[x]);
        cout<<x<<" ";
    }
}
int main()
{
    citire();
    dijkstra(1);
    for(int i=2; i<=n; i++)
    {
        cout<<d[i]<<" ";
    }

    return 0;
}