#include <fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int a[251000],b[251000],c[251000],d[51000],i,ok,m,n,u;
int main()
{ f>>n>>m;
    u=(1<<30);
    for(i=2;i<=n;i++)
        d[i]=u;
    for(i=1;i<=m;i++)
    {
        f>>a[i]>>b[i]>>c[i];
        if(a[i]==1)
            d[b[i]]=c[i];
    }
    ok=0;
    while(!ok)
    {
        ok=1;
        for(i=1;i<=m;i++)
            if(d[b[i]]>d[a[i]]+c[i])
            {
                d[b[i]]=d[a[i]]+c[i];
                ok=0;
            }
    }
    for(i=2;i<=n;i++)
        if(d[i]==u)
            g<<"0 ";
        else
            g<<d[i]<<' ';
    return 0;
}