#include<fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,c[500005],dist[50005],ok[50005];
struct nod
{
    int inf;
    int d;
    nod *adr;
} *v[50005];
void creare()
{
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        nod *p=new nod;
        p->inf=y;
        p->d=z;
        p->adr=v[x];
        v[x]=p;
    }
}
void bfs(int x)
{
    int pr,g;
    pr=g=1;
    c[pr]=x;ok[x]=1;
    while(pr<=g)
    {
        x=c[pr++];
        for(nod *p=v[x];p!=NULL;p=p->adr)
        {
            if(dist[x]+p->d<dist[p->inf])
            {
                dist[p->inf]=dist[x]+p->d;
                if(ok[p->inf]==0)
                {
                    ok[p->inf]=1;
                    c[++g]=p->inf;
                }
            }
        }
        ok[x]=0;
    }
}
int main()
{
    fin>>n>>m;
    creare();
    for(int i=2;i<=n;i++)
        dist[i]=250000025;
    bfs(1);
    for(int i=2;i<=n;i++)
    {
        if(dist[i]==250000025)
            fout<<0<<' ';
        else
            fout<<dist[i]<<' ';
    }
    return 0;
}