#include<fstream>
#include<cstdio>
#include<vector>
#include<utility>
#define ff it->first
#define ss it->second

using namespace std;
int n,m,a,b,c,h[50010],poz[50010],i,l,nod;
long d[50005],oo=500000000,dist;
void read(),solve(),percolate(int t),sift(int f);
vector <pair<long,long> > v[50010];

int main()
{

    read();
    solve();
    return 0;
}
void read()
{
    ifstream in("dijkstra.in");
    in>>n>>m;
    for(;m;m--)
    {
        in>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    in.close();
}
void solve()
{
    vector<pair<long,long> >::iterator it;
    ofstream out("dijkstra.out");
    for(i=1;i<=n;i++)
    {
        h[i]=0;
        d[i]=oo;
        poz[i]=0;
    }
    d[1]=0;
    l=1;
    h[1]=1;
    for(;l;)
    {
        nod=h[1];
        dist=d[nod];
        for(it=v[nod].begin();it!=v[nod].end();it++)
            if(d[ff]>dist+ss)
            {
                d[ff]=dist+ss;
                if(poz[ff]==0)
                {
                    l++;
                    h[l]=ff;
                    percolate(l);
                }
                else percolate(poz[ff]);
            }
        h[1]=h[l];
        poz[h[1]]=1;
        l--;
        sift(1);
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==oo)
            d[i]=0;
    }
    for(i=2;i<=n;i++)
        out<<d[i]<<" ";
    out.close();
}
void percolate(int f)
{
    int t,aux;
    for(;;)
    {
        t=f>>1;
        if(d[h[t]]<=d[h[f]] || t<1)
            return;
        aux=h[t];
        h[t]=h[f];
        h[f]=aux;
        poz[h[t]]=t;
        poz[h[f]]=f;
        f=t;
    }
}
void sift(int t)
{
    int f,aux;
    for(;;)
    {
        f=t<<1;
        if(f>l)
            return;
        if(f<l)
            if(d[h[f]]>d[h[f+1]])
                f++;
        if(d[h[t]]<d[h[f]])
            return;
        aux=h[t];
        h[t]=h[f];
        h[f]=aux;
        poz[h[t]]=t;
        poz[h[f]]=f;
        t=f;
    }
}