#include <fstream>
#include <iostream>
#define maxn 50010
#define maxm 250010
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,dist[maxn+5],Q[maxn+5],tail,head;
bool viz[maxn+5];
struct nod
{
    int info,cost;
    nod *urm;
}*v[maxn+5],*c,*e[maxn+5];
void adauga(int x)
{
    if(tail==n+1)
        tail=0;
    Q[tail]=x;
    tail++;
    viz[x]=1;
}
int main()
{
    int x,y,z;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->info=i;
        v[i]->urm=0;
        v[i]->cost=0;
        dist[i]=inf;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        if(!v[x]->urm)
        {
            c=new nod;
            c->info=y;
            c->urm=0;
            c->cost=z;
            v[x]->urm=c;
            e[x]=c;
        }
        else
        {
            c=new nod;
            c->info=y;
            c->urm=0;
            c->cost=z;
            e[x]->urm=c;
            e[x]=c;
        }
    }
    Q[0]=1;
    dist[1]=0;
    head=0,tail=1;
    while(head!=tail)
    {
        if(head>n)
            head=0;
        c=v[Q[head]];
        x=c->info;
        head++;
        viz[x]=0;
        while(c->urm)
        {
            c=c->urm;
            if(dist[x]+c->cost<dist[c->info])
            {
                dist[c->info]=dist[x]+c->cost;
                if(!viz[c->info])
                    adauga(c->info);
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(dist[i]==inf)
        fout<<0<<" ";
        else
        fout<<dist[i]<<" ";
    return 0;
}