#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

struct Node {
    int nr, dist;
    struct Node *next;
};

int n, m, parent[50001], dist[50001];
Node *lda[50001];
Node *r, *p, *v;

void add_edge(Node *&y, int x, int d){
    r = new Node;
    r->nr = x;
    r->dist = d;
    r->next = y;
    y = r;
}

void Dijkstra(int x){
    dist[x] = 0;
    parent[x] = -1;
    set<pair<int, int>> s;
    s.insert({0, x});
    while(!s.empty()){
        int a = s.begin()->second;
        s.erase(s.begin());
        for(Node *h = lda[a]; h != NULL; h = h->next){
            int b = h->nr, d = h->dist;
            if(dist[a] + d < dist[b]){
                s.erase({dist[b], b});
                dist[b] = dist[a] + d;
                s.insert({dist[b], b});
                parent[b] = a;
            }
        }
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, d;
        cin >> a >> b >> d;
        add_edge(lda[a], b, d);
        //add_edge(lda[b], a, d); //daca graful este neorientat
    }  
    for(int i = 0; i <= 50000; i++)
        dist[i] = 1e9;
    Dijkstra(1);
    for(int i = 2; i <= n; i++)
        cout << (dist[i] == 1e9 ? 0 : dist[i]) << ' ';
}  
 
int main(){
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}