#include<iostream>
#include<fstream>

using namespace std;
int n,m,c[1501][1501],d[5001];
void dijkstra(int x0)
{
    int min,i,j,ok,k;
    int viz[50000],tata[50000];
    for(i=1;i<=n;i++)
    {
        d[i]=c[x0][i];
        tata[i]=x0;
        viz[i]=0;
    }
    tata[x0]=0;
    viz[x0]=1;
    ok=1;
    while(ok)
    {
        min=33000;
        for(i=1;i<=n;i++)
            if(!viz[i] && min>d[i])
            {
                min=d[i];
                k=i;
            }
        if(min!=33000)
        {
            viz[k]=1;
            for(i=1;i<=n;i++)
                if(!viz[i] && d[i]>d[k]+c[k][i])
                {
                    d[i]=d[k]+c[k][i];
                    tata[i]=k;
                }
        }
        else
            ok=0;
    }
}
int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int a,b,i,j;
    fin>>n>>m;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                c[i][j]=33000;
    for(i=1;i<=m;i++)
    {
        d[i]=33000;
        fin>>a>>b;
        fin>>c[a][b];
    }
    dijkstra(1);
    for(i=2;i<=n;i++)
    {
        if(d[i]!=33000)
            fout<<d[i]<<" ";
        else fout<<0<<" ";
    }
    return 0;
}