#include <fstream>
#include <set>
#include <vector>
#define inf 250000*20000+1

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, i, a, b, c, d[50001], p;
vector<pair<int, int> > v[50001];
set<pair<int, int> > s;

int main(){
    fin>>n>>m;
    while(m--){
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b, c));
    }
    for(i=2;i<=n;i++)
        d[i] = inf;
    /// ce pun in set?
    /// costul drumului si nodul destinatie
    /// costul minim al unui drum aflat inca in set corespunde intotdeauna primului element din set
    s.insert(make_pair(0, 1));
    while(!s.empty()){
        p = s.begin()->second;
        s.erase(s.begin());
        for(i=0;i<v[p].size();i++)
            if(d[v[p][i].first] > d[p] + v[p][i].second){
                s.erase(make_pair(d[v[p][i].first], v[p][i].second));
                d[v[p][i].first] = d[p] + v[p][i].second;
                s.insert(make_pair(d[v[p][i].first], v[p][i].first));
            }
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";
    return 0;
}