#include <bits/stdc++.h>

using namespace std;

string name ="dijkstra";

ifstream fin(name+".in");
ofstream fout(name + ".out");


struct Edge{
    int x,cost;
    Edge(){}
    Edge(int x, int cost){
        this->x = x;
        this->cost = cost;
    }
    bool operator<(const Edge &e)const{
        return this->cost>e.cost;
    }
};


vector<vector<Edge>> grph = vector<vector<Edge>>(51000);
vector<int> d = vector<int>(51000,INT_MAX);
vector<int> vis = vector<int>(51000,0);
priority_queue<Edge>q;


void dijktra(int x){

    q.push(Edge(x,0));
    while (!q.empty()){
        Edge e = q.top();
        q.pop();
        d[x] = 0;
        vis[e.x] = 1;
        for (const auto &item: grph[e.x]) {
            if(vis[item.x]==0){
                if(d[e.x]+item.cost <= d[item.x]){
                    d[item.x] = d[e.x] + item.cost;
                    q.push(item);
                }
            }

        }

    }


}





int main(){
    int n,m;
   fin>>n>>m;

    for(int i=0;i<m;++i){
        int x,y,z;
        fin>>x>>y>>z;
        grph[x].push_back(Edge(y,z));
    }

    dijktra(1);

    for (int i=2;i<=n;i++) {
        fout<<(d[i]==INT_MAX?0:d[i])<<" ";

    }

}