#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;
    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].first));
                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++){
        if(d[i] == inf)
            d[i] = 0;
        fout<<d[i]<<" ";}
    return 0;
}