#include <fstream>
#include <vector>
#define INF 2000000001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct nod
{
    int dist,ind;
}a[50011];
bool cmp(nod a,nod b)
{
    return a.dist<b.dist || (a.dist==b.dist && a.ind<b.ind);
}
int n,coord[50011];
void insus(int k)
{
    if(k>1)
    {
    if(cmp(a[k],a[k/2])==1)
    {
        coord[a[k].ind]=k/2;
        coord[a[k/2].ind]=k;
        swap(a[k],a[k/2]);
        insus(k/2);
    }
    }
}
void injos(int k)
{
    int k1=k*2;
    if(k1<=n)
    {
    if(k1<n && cmp(a[k1+1],a[k1])==1)
        k1++;
    if(cmp(a[k],a[k1])==0)
    {
        coord[a[k].ind]=k1;
        coord[a[k1].ind]=k;
        swap(a[k],a[k1]);
        injos(k1);
    }
    }
}
vector <pair<int,int>> v[50011];
int m,k,x,y,z,d[50011],i,p,nn;
int main()
{
    f>>n>>m;
    nn=n;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }
    for(i=1;i<=n;i++)
    {
        d[i]=INF;
        a[i]={INF,i};
        coord[i]=i;
    }
    k=1;
    d[k]=0;
    a[coord[k]].dist=0;
    insus(coord[k]);
    while(n)
    {
        p=a[1].ind;
        coord[p]=-1;
        a[1]=a[n];
        n--;
        injos(1);
        for(i=0;i<v[p].size();i++)
        {
            if(d[v[p][i].first]>d[p]+v[p][i].second)
            {
                d[v[p][i].first]=d[p]+v[p][i].second;
                if(coord[v[p][i].first]!=-1)
                {
                a[coord[v[p][i].first]].dist=d[p]+v[p][i].second;
                insus(coord[v[p][i].first]);
                }
            }
        }
    }
    for(i=2;i<=nn;i++)
    {
        if(d[i]!=INF)
        g<<d[i]<<" ";
        else
        g<<0<<" ";
    }
    return 0;
}