#include <iostream>
#include <fstream>
#include <vector>
#define N 51000
#define M 251000


using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

vector <short> a[N],b[N];
short minim[N],st[M],dr[M],cost[M],poz[M],h[M];





void swap(short a,short b)
{
    short c=h[a];
    h[a]=h[b];
    h[b]=c;
    poz[h[a]]=a;
    poz[h[b]]=b;
}


void urca(short p)
{
    while(p!=1 && cost[h[p]]<cost[h[p/2]])
    {
        swap(p,p/2);
        p=p/2;
    }
}

void coboara(short p)
{
    short ps=p;
    if(p*2<=h[0] && cost[h[ps]]>cost[h[p*2]])
        ps=p*2;
    if(p*2+1<=h[0] && cost[h[ps]]>cost[h[p*2+1]])
        ps=p*2+1;
    if(ps!=p)
    {
        swap(ps,p);
        coboara(ps);
    }

}


void baga(short x)
{
    h[++h[0]]=x;
    poz[x]=h[0];
    urca(h[0]);
}

void scoate(short x)
{
    h[poz[x]]=h[h[0]];
    poz[h[h[0]]]=poz[x];
    h[0]--;
    urca(poz[x]);
    coboara(poz[x]);
}

int main()
{
    int n,m,i,x,j;
    in>>n>>m;
    for(i=1;i<=m;++i)
    {
         in>>st[i]>>dr[i]>>cost[i];
         a[st[i]].push_back(i);
         b[dr[i]].push_back(i);
    }
    for(i=1;i<=n;++i)
    {
        minim[i]=-1;
    }
    for(i=0;i<a[1].size();++i)
    {
        baga(a[1][i]);
    }
    minim[1]=0;
    for(i=2;i<=n;++i)
    {
        x=h[1];
        minim[dr[x]]=minim[st[x]]+cost[x];
        for(j=0;j<b[dr[x]].size();++j)
        {
            if(poz[b[dr[x]][j]])
            {
                scoate(b[dr[x]][j]);
                poz[b[dr[x]][j]]=0;
            }
        }
        for(j=0;j<a[dr[x]].size();++j)
        {
            if(minim[dr[a[dr[x]][j]]]==-1)
                baga(a[dr[x]][j]);
        }
    }
    for(i=2;i<=n;++i)
    {
        if (minim[i]==-1)
            out<<"0 ";
        else
            out<<minim[i]<<" ";
    }
    return 0;
}