#include<iostream>
#include<fstream>
#include<vector>
#define DX 50010
#define INF 2000000000
using namespace std;
fstream fin("dijkstra.in",ios::in),fout("dijkstra.out",ios::out);
int cost[DX],h[DX],unde[DX],lh,n,m,nr;
vector <pair<int,int> > v[DX];
void up(int nod)
{
    int tata=nod/2;
    while(nod!=1 && cost[h[nod]]<cost[h[tata]])
    {
        swap(h[nod],h[tata]);
        swap(unde[h[nod]],unde[h[tata]]);
        nod=tata;
        tata=nod/2;
    }
}
void down(int nod)
{
    int plod,fiu1,fiu2,ok=0;
    do
    {
        fiu1=nod*2;
        fiu2=fiu1+1;
        plod=ok=0;
        if(fiu1<=lh)
        {
            plod=fiu1;
            if(fiu2<=lh && cost[h[fiu2]]<cost[h[fiu1]]) plod=fiu2;
        }
        if(plod!=0 && cost[h[plod]]<cost[h[nod]])
        {
            ok=1;
            swap(h[nod],h[plod]);
            swap(unde[h[nod]],unde[h[plod]]);
            nod=plod;
        }
    }while(ok==1);
}
void dijkstra()
{
    int i,j,b,aux,c,pmin;
    while(lh!=0)
    {
        pmin=h[1];
        c=cost[pmin];
        swap(h[1],h[lh]);
        unde[h[1]]=1;
        unde[pmin]=0;
        lh--;
        down(1);
        for(j=0;j<v[pmin].size();j++)
        {
            aux=c+v[pmin][j].second;
            b=v[pmin][j].first;
            if(cost[b]>aux)
            {
                cost[b]=aux;
                if(unde[b]==0)
                {
                    lh++;
                    unde[b]=lh;
                    h[lh]=b;
                }
                up(unde[b]);
            }
        }
    }
}
int main()
{
    int a,b,c,i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    for(i=1;i<=n;i++) cost[i]=INF;
    h[lh=1]=1;
    unde[1]=1;
    cost[1]=0;
    dijkstra();
    for(i=2;i<=n;i++)
    {
        if(cost[i]!=INF)
            fout<<cost[i]<<" ";
        else
            fout<<"0 ";
    }
}