#include <fstream>
#include <vector>
#define INF 1000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct nume{
    int vec,cost;
};
int s[50001],d[50001],heap[50002],ult,poz[50002];
vector <nume> a[50001];
void pop(int x)
{
    int i,aux1;
    i=poz[x];
    if(i==0)
        i=ult+10;
    if(i>ult)
        return;
    if(i==ult)
    {
        ult--;
        return ;
    }
    aux1=heap[i];
    poz[heap[ult]]=poz[x];
    heap[i]=heap[ult];
    ult--;
    int aux=0;
    while(i!=aux)
    {
        aux=i;
        if(i*2>ult){
            poz[x]=0;
            return ;
        }
        if(i*2==ult)
        {
            if(d[heap[i]]>d[heap[i*2]])
            {
                 swap(poz[heap[i*2]],poz[heap[i]]);
                 swap(heap[i],heap[i*2]);
                 poz[x]=0;
                 return;
            }
        }
        if(d[heap[i*2]]>d[heap[i*2+1]] && d[heap[i*2+1]]<d[heap[i]])
        {
            swap(poz[heap[i*2+1]],poz[heap[i]]);
            swap(heap[i],heap[i*2+1]);
            i=i*2+1;
        }
        else
        {
            if(d[heap[i*2]]<d[heap[i]])
            {
                swap(poz[heap[i*2]],poz[heap[i]]);
                swap(heap[i],heap[i*2]);
                i=i*2;
            }
        }
    }
    poz[aux1]=0;
}
void push(int x)
{
    int i;
    heap[++ult]=x;
    i=ult;
    poz[x]=ult;
    while(i!=1)
    {
        if(d[heap[i/2]]>d[heap[i]])
        {
            swap(poz[heap[i/2]],poz[heap[i]]);
            swap(heap[i/2],heap[i]);
            i=i/2;
        }
        else
            {
                poz[x]=i;
                return;
            }
    }
    poz[x]=i;
}
int main()
{
    int n,i,j,m,x,y,ind,minim,c;
    nume var;
    fin>>n;
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        var.vec=y;var.cost=c;
        a[x].push_back(var);
    }
    s[1]=1;
    for(i=2;i<=n;i++)
        d[i]=INF;
    j=0;
    for(j=0;j<a[1].size();j++)
    {
        i=a[1][j].vec;
        d[i]=a[1][j].cost;
        push(i);
    }
    for(int k=2;k<=n;k++)
    {
        ind=heap[1];pop(heap[1]);
        minim=d[ind];
        s[ind]=1;
        j=0;
        for(j=0;j<a[ind].size();j++)
        {
            i=a[ind][j].vec;
            if(d[i]>minim+a[ind][j].cost)
            {
                pop(i);
                d[i]=minim+a[ind][j].cost;
                push(i);
            }
        }
    }
    for(i=2;i<=n;i++)
        if(d[i]!=INF)
        {
            fout<<d[i]<<' ';
        }
        else
            fout<<0<<' ';
    return 0;
}