#include <iostream>
#include <fstream>
#define infinit 9999999
#define nmax 110
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int M[nmax][nmax],n,m,p,D[nmax];
void dijkstra(int x0);
int main()
{
    int i,j,x,y,v;
    fin>>n>>m; p=1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            M[i][j]=infinit;
        M[i][i]=0;
    }
    while(fin>>x>>y>>v)
        M[x][y]=v;
    dijkstra(p);
    for(i=2;i<=n;i++)
        if(D[i]!=infinit) fout<<D[i]<<' ';
        else fout<<"0 ";
    return 0;
}

void dijkstra(int x0)
{
    int i,k,ok,minim,viz[nmax];
    for(i=1;i<=n;i++)
    {
        D[i]=M[x0][i];
        viz[i]=0;
    }
    D[x0]=0; viz[x0]=1; ok=1;
    while(ok)
    {
        minim=infinit;
        for(i=1;i<=n;i++)
            if(!viz[i]&&minim>D[i])
            {
                minim=D[i];
                k=i;
            }
        if(minim!=infinit)
        {
            viz[k]=1;
            for(i=1;i<=n;i++)
                if(!viz[i]&&D[i]>D[k]+M[k][i])
                    D[i]=D[k]+M[k][i];
        }
        else ok=0;
    }
}