#include <iostream>
#include <bits/stdc++.h>

#define in_file "dijkstra.in"
#define out_file "dijkstra.out"
#define NMAX 50005
#define INF 1000003

using namespace std;

vector<pair<int, int>> G[NMAX];
void printVec(vector<int> v){
    for(auto e : v){
        fprintf(stdout, "%d, ", e);
    }
}

void dij(int node,int n){
    vector<int> dist(n+1, INF);
    priority_queue<pair<int, int>> h;
    h.push({0, node});
    while(!h.empty()){
        int curNode = h.top().second;
        int curDist = -h.top().first;
        h.pop();
        if(curDist!=dist[curNode]) continue;
        for(auto c:G[curNode]){
            if(dist[c.first]>=curDist + c.second){
                 dist[c.first] = curDist + c.second;
                 h.push({-dist[c.first], c.first});
            }
        }
    }
    for(int i=2; i<=n; i++){
        cout<<dist[i]==INF ? 0 : dist[i]<<" ";
    }
}
int main()
{
    freopen(in_file, "r", stdin);
    freopen(out_file, "w", stdout);
    int n, m;
    int n1, n2, cost;
    cin>>n>>m;
    while(m--){
        cin>>n1>>n2>>cost;
        G[n1].push_back({n2, cost});
    }

    dij(1,n);
    return 0;
}