#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int INF = 2e9;
const int MAX_N = 50005;
int n, m, a, b, c;
int dist[MAX_N];

struct edge{
    int nxt;
    int cst;
}; vector <edge> e[MAX_N];

struct drum{
    int nod;
    int total;
} crt;

inline bool operator < (const drum &lhs, const drum &rhs){
    return lhs.total < rhs.total;
}

set <drum> best;

bitset <MAX_N> viz;
void dijkstra(int start){
    dist[1] = 0;
    for(int i=2; i<=n; i++)
        dist[i] = INF;

    best.insert({1, dist[1]});
    while(!best.empty()){
        crt = *best.begin();
        best.erase(best.begin());

        if(!viz[crt.nod])
            for(auto vecin : e[crt.nod])
                if(dist[vecin.nxt] > crt.total + vecin.cst){
                    dist[vecin.nxt] = crt.total + vecin.cst;
                    best.insert({vecin.nxt, dist[vecin.nxt]});
                }
        viz[crt.nod] = true;
    }
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n>>m;
    for(int i=1; i<=m; i++){
        fin>>a>>b>>c;
        e[a].push_back({b, c});
    }

    dijkstra(1);

    for(int i=2; i<=n; i++)
        fout<<dist[i]<<" ";
    return 0;
}