#include <cstdio>
#include <vector>
#include <queue>
#include <cstring> // pt memset
#define N 50001
using namespace std;
int n, m, d[N];
vector < pair<int, int> >a[N];//ai eroare aici
void read(){
    freopen("dijkstra.in", "r", stdin);
    scanf("%d %d ", &n, &m);
    int x, y, z;
    for(int i = 1; i <= m; ++i){
        scanf("%d %d %d ", &x, &y, &z);
        //si cum fac a[x] sau cum?la bfs cum faceai?a[p].push_back(q)
        // bun, p e x aici, iar q trebuie sa fie un pair
        a[x].push_back( make_pair(y, z) );
    }
}
void solve(){
    queue <int> Q;
    // cine e sursa?1 bun
    Q.push(1);
    memset (d, 0x3f3f3f3f, sizeof(d));
    d[1] = 0;
    while(!Q.empty()){
        int x = Q.front();
        Q.pop();
        for(int i = 0; i < a[x].size(); ++i) {
            int y = a[x][i].first; // nodul adiacent
            int c = a[x][i].second; // costul muchiei
            if (d[x] + c < d[y]) {// daca obtinem un drum mai scurt
                d[y] = d[x] + c;
                Q.push(y);
            }
        }
      
    }//trebuie sa mai afisez tu ce crezi da:D afiseaza?
    for(int i = 2; i <= n; ++i)
        printf("%d ", d[i] == 0x3f3f3f3f ? 0 : d[i]);
    printf("\n");
}//trimit?da
int main(){
    freopen("dijkstra.out", "w", stdout);
    read();
    solve();
    return 0;
}
//pai noi o luam infint :))da