//dijkstra cu make_heap
#include<cstdio>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<string>
#include<sstream>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
using namespace std;

//ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define _PARSARE_
#ifdef _PARSARE_
//////////////////////////////////////////////////////////////
//parsarea citirii
//////////////////////////////////////////////////////////////
#define DIM 8192
char buff[DIM+16];
int idx;

//numere NATURALE:
inline void cit_uint(int &x)
{
    x=0;
    while(buff[idx]<'0' || buff[idx]>'9')
        if(++idx==DIM)fread(buff, 1, DIM, stdin), idx=0;
    while(buff[idx]>='0' && buff[idx]<='9') {
        x=x*10+buff[idx]-'0';
        if(++idx==DIM)fread(buff,1, DIM, stdin),idx=0;
    }
}

//numere INTREGI:
inline void cit_int(int &x)
{
    x=0;
    while((buff[idx]<'0' || buff[idx]>'9') && (buff[idx]!='-'))
        if(++idx==DIM)fread(buff, 1, DIM, stdin), idx=0;

    int neg=0;
    if(buff[idx]=='-') {
        neg=1;
        if(++idx==DIM)fread(buff, 1, DIM, stdin),idx=0;
    }

    while(buff[idx]>='0' && buff[idx]<='9') {
        x=x*10+buff[idx]-'0';
        if(++idx==DIM)fread(buff,1, DIM, stdin),idx=0;
    }
    if(neg) x=-x;
}
#endif //_PARSARE_

struct muchie {
    int vec,cost;
};

vector <muchie> G[50000+10];
int viz[50000+10],d[50000+10];
bool cmp(const pair<int,int> &a, const pair<int,int> &b)
{
    if(a.first == b.first)
        return a.second<b.second;
    return a.first<b.first;
}
inline void dijkstra()
{
    memset(d,0x3f,sizeof(d));
//    priority_queue < pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > Q;
    vector<pair<int,int> > V;
    d[1]=0;
    V.push_back(make_pair(0,1));
    while(!V.empty()) {
        int nod=V[0].second,cost=V[0].first;
        pop_heap(V.begin(),V.end(),greater<pair<int,int> >());
        V.pop_back();
        for(vector<muchie>::iterator it=G[nod].begin(),stop=G[nod].end(); it<stop; ++it) {
            if( d[it->vec] > cost + it->cost ) {
                d[it->vec] = cost + it->cost;
                V.push_back( make_pair( d[it->vec], it->vec ) );
                push_heap(V.begin(),V.end(),greater<pair<int,int> >());
            }
        }
    }

}
int main()
{
    freopen("dijkstra.in","r",stdin);
    int n,m;

//    fin>>n>>m;
    cit_int(n);
    cit_int(m);
    for(int i=1; i<=m; ++i) {
        int from,to,cost;
//        fin>>from>>to>>cost;
        cit_int(from);
        cit_int(to);
        cit_int(cost);
        G[from].push_back((muchie) {
            to,cost
        });
    }
    dijkstra();

    for(int i=2; i<=n; ++i)
        fout<<((d[i]==0x3f3f3f3f)?0:d[i])<<' ';
    putchar('\n');

    return 0;
}