#include <fstream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct graf
{
    int nod,cost;
    graf *leg;
};
graf *G[50001];
int n,m;
bool viz[50001];
int coada[100001],d[50001],t[50001];

void add(int x,int y,int q)
{
    graf *p=new graf;
    p->nod=y;
    p->cost=q;
    p->leg=G[x];
    G[x]=p;

}
void bellman()
{
    int inc=1,sf=1;
    int i;
    for(i=2;i<=n;i++)
        d[i]=1000001;
    coada[1]=1;
    viz[1]=true;
    bool ciclu=false;
    t[1]=1;
    while(inc<=sf and !ciclu)
    {
        for(graf *p=G[coada[inc]];p;p=p->leg)
            if(d[p->nod]>d[coada[inc]]+p->cost)
        {
            t[p->nod]++;
            d[p->nod]=d[coada[inc]]+p->cost;
            if(!viz[p->nod])
            {
                coada[++sf]=p->nod;
                viz[p->nod]=true;
            }
        }
        viz[coada[inc]]=false;
        if(t[coada[inc]]>=n)
            ciclu=true;
        inc++;
    }
}
int main()
{
    int x,y,q;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>q;
        add(x,y,q);
    }
    bellman();
    for(int i=2;i<=n;i++)
        if(d[i]==1000001)
            g<<"0 ";
        else g<<d[i]<<' ';
    return 0;
}