#include <iostream>
#include <fstream>
#define MAX 10000000
using namespace std;
int n,m,i,d[50001],nod,viz[50001],x,y,c,a[1001][1001],ok,maxi,k;
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=1;i<=n;i++)d[i]=MAX;
    nod=1;
    viz[nod]=1;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
        if(x==nod)d[y]=c;
    }
    ok=1;
    while(ok)
    {
        ok=0;
        maxi=MAX;
        for(i=1;i<=n;i++)if(viz[i]==0&&d[i]<maxi)
        {
            ok=1;
            maxi=d[i];
            k=i;
        }
        viz[k]=1;
        for(i=1;i<=n;i++)if(i!=nod&&a[k][i]!=0)
        {
            if(a[k][i]+d[k]<d[i])d[i]=a[k][i]+d[k];
        }
    }
    for(i=1;i<=n;i++)if(i!=nod)
    {
        if(d[i]!=MAX)g<<d[i]<<' ';
        else g<<0<<' ';
    }
    f.close();
    g.close();
}