#include <bits/stdc++.h>
#define ll long long
#define sz size
#define pb push_back
#define er erase
#define in insert
#define fr first
#define sc second
#define mp make_pair
#define pi pair
#define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
#define rc(s) return cout<<s,0
const int mod=1e9+7;
const int inf=1e5;
using namespace std;
std::multiset< pair<ll,ll> >::iterator it;
std::multiset< pair<ll,ll> >::iterator it1;

vector<pair<long long,long long> >nod[50005];
multiset<pair<long long,long long> >noto;
long long m,n,x,y,z,d[50005];


int main(){ _
    ifstream fin ("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin >> n >> m;
    while(m--){
        fin >> x >> y >> z;
        nod[x].push_back(make_pair(y,z));
    }
    for(int i=2;i<=n;i++){
        d[i]=1000000000000000000;
    }

    noto.insert(make_pair(0,1));
    while(noto.empty()==false){
        it=noto.begin();
        x=it->second;
        y=it->first;
        noto.erase(noto.begin());
        for(int i=0;i<nod[x].size();i++){
            if(d[x]+nod[x][i].second<d[nod[x][i].first]){
                if(d[nod[x][i].first]!=1000000000000000000) noto.erase(noto.find(make_pair(d[nod[x][i].first],nod[x][i].first)));
                d[nod[x][i].first]=d[x]+nod[x][i].second;
                noto.insert(make_pair(d[nod[x][i].first],nod[x][i].first));
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(d[i]!=1000000000000000000)fout<<d[i]<<' ';
        else fout<<'0'<<' ';
    }
}