#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
const int maxim=1<<31-1;

class compare{
    vector<int>& cost;
public:
    compare(vector<int>& Cost):
        cost(Cost){}
    bool operator()(const int& a,const int& b){
        return cost[a]<cost[b];
    }
};

int main(){
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    int n,m;
    in>>n>>m;
    vector<vector<pair<int,int> > > v(n);
    vector<bool> visited(n,false);
    vector<int> cost(n,maxim);
    for(int i=0;i<m;i++){
        int x,y,c;
        in>>x>>y>>c;
        v[x-1].push_back(make_pair(y-1,c));
    }
    compare c(cost);
    set<int,compare> q(c);

    cost[0]=0;
    q.insert(0);
    while(!q.empty()){
        int ref=*q.begin();
        q.erase(q.begin());
        visited[ref]=true;

        for(int i=0;i<v[ref].size();i++){
            if(!visited[v[ref][i].first]){
                if(cost[v[ref][i].first]>v[ref][i].second+cost[ref]){
                    cost[v[ref][i].first]=v[ref][i].second+cost[ref];
                    q.insert(v[ref][i].first);
                }
            }
        }
    }

    for(int i=1;i<n;i++){
        if(cost[i]==maxim) {
            out<<"0 ";
        }else out<<cost[i]<<" ";
    }
}