#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)
{
    return (nod*2);
}
inline int dr(int nod)
{
    return (nod*2+1);
}
inline int tata(int nod)
{
    return (nod/2);
}
inline void push(int nod,int pr)
{
    bin_heap auxx;
    auxx.poz=nod;auxx.pr=pr;
    int poz=++lv;
    v[poz]=auxx;
    while(v[poz].pr<v[tata(poz)].pr && poz>1)///cand se face poz=1 sigur nu o sa fie mai mic decat 0
    {
        swap(v[poz],v[tata(poz)]);
        poz=tata(poz);
    }
    return;
}
inline bin_heap pop()
{
    bin_heap auxx=v[1];
    int poz=1;
    v[poz]=v[lv];
    lv--;
    while((st(poz)<=lv || dr(poz)<=lv) && poz<=lv)
    {
        if(v[poz].pr<=v[st(poz)].pr && v[poz].pr<=v[dr(poz)].pr)break;
        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);
        }
    }
    return auxx;
}
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;
        noduri aux2=nd[aux.poz];
        for(i=0;i<aux2.vec.size();i++)
            if(tr[aux2.vec[i]]==0)
            {
                int dist=mn[aux.poz]+aux2.dist[i];
                if(dist<mn[aux2.vec[i]])
                {
                    mn[aux2.vec[i]]=dist;
                    push(aux2.vec[i],dist);
                }
            }
    }
    for(i=2;i<=n;i++)
    {
        int ans=mn[i];
        if(ans==INT_MAX)ans=0;
        g<<ans<<" ";
    }
    f.close();
    g.close();
}