#include <fstream>
#define inf 999999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m, x, y, k, dist, R, d[50001], t[50001], s[50001];
struct nod
{
    nod *next;
    int info, dist;
}*p[50001], *u[50001];
int cautak()
{
    int kmin=inf, poz=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]<kmin&&s[i]==0)
        {
            kmin=d[i];
            poz=i;
        }
    }
    return poz;
}
void adauga(nod *&p, nod *&u, int x, int d)
{
    nod *c = new nod;
    c->info=x;
    c->dist=d;
    c->next=0;
    if(p==0)
    {
        p=c;
        u=c;
    }
    else
    {
        u->next=c;
        u=c;
    }
}
int main()
{
    fin>>n>>m;
    R=1;
    for(int i=1;i<=n;i++)
    {
        d[i]=inf;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>dist;
        adauga(p[x], u[x], y, dist);
    }
    for(nod *q=p[R]; q!=NULL; q=q->next)
    {
        d[q->info]=q->dist;
        t[q->info]=R;
    }
    s[R]=1;
    k=cautak();
    while(k)
    {
        for(int i=1;i<=n;i++)
        {
            for(nod *q=p[k];q!=NULL;q=q->next)
            {
                if(q->info==i&&d[i]>d[k]+q->dist)
                {
                    d[i]=d[k]+q->dist;
                    t[i]=k;
                }
            }
        }
        s[k]=1;
        k=cautak();
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==inf)
        {
            fout<<"0 ";
        }
        else
        fout<<d[i]<<' ';
    }
    fin.close();
    fout.close();
    return 0;
}