#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <list>
#include <climits>

FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

const int inf=INT_MAX/2;
#define next first
#define cost second

using namespace std;
int viz[50001],T[50001],n,m;
pair<int,int>D[50001],minQuery[50001];

list< pair <int,int> > lv[250002];

void get_graph()
{
    int a,b,c;
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        lv[a].push_front(make_pair(b,c));
    }
}

struct cmp
{
    bool operator()(const pair<int,int> a,const pair<int,int> b)const
    {
        return a.first>b.first;
    }
};

void dykstra(int k)
{
    int i;
    list< pair <int,int> > ::iterator it;
    viz[k]=1;D[k]=make_pair(0,k);
    for(i=1;i<=n;++i)if(i-k)D[i]=make_pair(inf,i);
    for(it=lv[k].begin();it!=lv[k].end();++it)
        D[(*it).next].first=(*it).cost,T[(*it).next]=k;
    int pz,vmax,okay=1;
    for(i=1;i<=n;++i)
    {
        memcpy(minQuery,D,sizeof(D));
        make_heap(minQuery+2,minQuery+n+1,cmp());
        pz=minQuery[2].second;
        vmax=n;
        while(viz[pz])
        {
            pop_heap(minQuery+2,minQuery+vmax+1,cmp());
            pz=minQuery[2].second;
            if(vmax==1)
            {
                okay=0;
                break;
            }
            vmax--;

        }
        if(!okay)break;
        viz[pz]=1;
        for(it=lv[pz].begin();it!=lv[pz].end();++it)
            if(!viz[(*it).next] && D[pz].first+(*it).cost < D[(*it).next].first)
                         D[(*it).next].first = D[pz].first+(*it).cost,T[(*it).next]=pz;
    }
    for(i=2;i<=n;++i)
        fprintf(g,"%d ",D[i].first);
}

int main()
{
    get_graph();
    dykstra(1);
    return 0;
}