#include<iostream>
#include<fstream>

using namespace std;
int c[5000][5000],n,m,d[50000];
void dijkstra(int x)
{
    int i,j,min,k,ok;
    int viz[50000],tata[50000];
    for(i=1;i<=n;++i)
    {
        d[i]=c[x][i];
        tata[i]=x;
        viz[i]=0;
    }
    tata[x]=0;
    viz[x]=1;
    ok=1;
    while(ok)
    {
        min=99999;
        for(i=1;i<=n;++i)
            if(!viz[i] && min>d[i])
            {
                min=d[i];
                k=i;
            }
        if(min!=99999)
        {
            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 i,a,b,j;
    fin>>n>>m;
     for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            c[i][j]=99999;
    for(i=1;i<=m;++i)
    {
        d[i]=999999;
        fin>>a>>b;
        fin>>c[a][b];
    }
    dijkstra(1);
    for(i=1;i<=n;++i)
    {
        /*for(j=1;j<=n;++j)
            fout<<c[i][j]<<" ";
        fout<<"\n";*/
        if(d[i]!=99999)
            fout<<d[i]<<" ";
    }
    return 0;
}