#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct noduri{vector <int> vec;vector <int> dist;}nd[50003];
struct bin_heap{int poz;int pr;}v[50003];///binary min_heap
int i,n,m,lv,cttr=0;
bool tr[50003]={0};
int mn[50003];
inline int st(int nod)
{
    int stg=nod*2;
    return stg;
}
inline int dr(int nod)
{
    int drn=nod*2+1;
    return drn;
}
inline int tata(int nod)
{
    int tat=nod/2;
    return tat;
}
void push(int nod,int pr)
{
    bin_heap aux;
    aux.poz=nod;aux.pr=pr;
    int poz=++lv;
    v[poz]=aux;
    while(v[poz].pr<v[tata(poz)].pr)///cand se face poz=1 sigur nu o sa fie mai mic decat 0
    {
        swap(v[poz],v[tata(poz)]);
        poz=tata(poz);
    }
    return;
}
bin_heap pop()
{
    bin_heap aux=v[1];
    int poz=1;
    v[poz]=v[lv];
    while((v[poz].pr>v[st(poz)].pr && st(poz)<=lv) || (v[poz].pr>v[dr(poz)].pr && dr(poz)<=lv))
    {
        if(v[st(poz)].pr<v[dr(poz)].pr)
        {
            swap(v[poz],v[st(poz)]);
            poz=st(poz);
        }
        else
        {
            swap(v[poz],v[dr(poz)]);
            poz=dr(poz);
        }
    }
    lv--;
    return aux;
}
int main()
{
    f>>n>>m;
    for(i=2;i<=n;i++)mn[i]=INT_MAX;
    for(i=1;i<=m;i++)
    {
        int x,y,dist;
        f>>x>>y>>dist;
        nd[x].vec.push_back(y);
        nd[x].dist.push_back(dist);
    }
    cttr=1;tr[1]=1;mn[1]=0;
    push(1,0);
    while(lv>0)
    {
        bin_heap aux=pop();
        cttr++;
        tr[aux.poz]=1;
        for(i=0;i<nd[aux.poz].vec.size();i++)
            if(tr[nd[aux.poz].vec[i]]==0)
            {
                int dist=mn[aux.poz]+nd[aux.poz].dist[i];
                if(dist<mn[nd[aux.poz].vec[i]])
                {
                    mn[nd[aux.poz].vec[i]]=dist;
                    push(nd[aux.poz].vec[i],dist);
                }
            }
    }
    for(i=2;i<=n;i++)
    {
        int ans=mn[i];
        if(ans==INT_MAX)ans=0;
        g<<ans<<" ";
    }
}