#include <fstream>
#include <iostream>
#include <set>
#include <list>
#include <vector>
#define maxn 0x3f3f3f3f
using namespace std;
int main(){
    int x, y, c, n, m, i, st;
    vector<int> d, pred;
    vector<bool> viz;
    vector<list<pair<int, int> > > L;
    list<pair<int, int> > E; //solutie
    ifstream fin("dijkstra.in");
    ofstream out("dijkstra.out");
    fin >> n >> m;
    pred.resize(n+1);
    d.resize(n+1, maxn);
    viz.resize(n+1,false);
    L.resize(n+1);
    for(i=0;i<m;i++){
        fin >> x >> y >> c;
        L[x].push_back(make_pair(c,y));
        //L[y].push_back(make_pair(c,x));
    }


    d[1] = 0;
    pred[1] = 0;
    set<pair<int,int> > Q;
    Q.insert(make_pair(d[1],st));

    while(!Q.empty()){
        int nod = Q.begin()->second;
        Q.erase(Q.begin());
        if(!viz[nod]){
            if(pred[nod]) E.push_back(make_pair(nod,pred[nod]));
            viz[nod] = true;
            for(pair<int,int>x:L[nod])
                if(!viz[x.second]){
                    if(d[x.second] > x.first + d[nod])
                        d[x.second] = x.first + d[nod];
                    pred[x.second] = nod;
                    Q.insert(x);
                }
        }
    }
    for(int i=1;i<=n;i++)
        out << d[i] << ' ' ;
return 0;
}