#include <bits/stdc++.h>
#define ll long long
using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

const int N_MAX = 50005;

vector<pair<int , int>>g[N_MAX];
int n , m , d[N_MAX] , lg[N_MAX];
bool used[N_MAX];

void solve (int start){
    queue<pair<int , int>>q;
    for (int i=1; i<=n; i++){
        d[i] = 1e9;
    }
    d[start] = 0;
    q.push({start , 0});
    while (q.empty() == false){
        int node = q.front().first , costActual = q.front().second;
        q.pop();
        used[node] = false;
        if (costActual > d[node]) continue;
        for (int i=0; i<lg[node]; i++){
            int new_node = g[node][i].first , new_cost = g[node][i].second;
            if (d[new_node] > d[node] + new_cost){
                d[new_node] = d[node] + new_cost;
                if (used[new_node] == false){
                    q.push({new_node , d[new_node]});
                    used[new_node] = true;
                }
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    fin >> n >> m;
    for (int i=1; i<=m; i++){
        int x , y , cost; fin >> x >> y >> cost;
        g[x].push_back({y , cost});
    }
    for (int i=1; i<=n; i++){
        lg[i] = (int)g[i].size();
    }
    solve(1);
    for (int i=2; i<=n; i++){
        if (d[i] == 1e9){
            d[i] = 0;
        }
        fout << d[i] << " ";
    }
}