#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct nod
{
    int info, cost;
    nod *urm;
}*a[100005];
int d[100005],used[100005],c[300005];
void adaugare(int x,int cos, nod *&prim)
{
    nod *p=new nod;
    p->info=x;
    p->cost=cos;
    p->urm=prim;
    prim=p;
}
void dijkstra(int k)
{
    d[k]=0;
    used[k]=1;
    int p,u;
    p=u=1;
    c[p]=k;
    while(p<=u)
    {
        int x=c[p++];
        used[x]=0;
        for( nod *p=a[x];p;p=p->urm)
            {if(d[p->info]>d[x]+p->cost)
        {

            d[p->info]=d[x]+p->cost;
            if(!used[p->info])c[++u]=p->info,used[p->info]=1;
        }
            }
    }
}
int n,m,v;
int main()
{
    fin>>n>>m;
    while(m)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        adaugare(y,cost,a[x]);

        --m;
    }
    for(int i=2;i<=n;++i)d[i]=inf;
    dijkstra(1);
    for(int i=2;i<=n;++i,fout<<" ")if(d[i]==inf)fout<<0;else fout<<d[i]<<" ";
    return 0;
}