#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define NMAX 50005
#define INFINIT 20005
typedef pair<int,int>ii;
vector<ii> a[NMAX];
int n, m, sol[NMAX], point[NMAX];
int x, y, i, d;
ii temp;

void Daijstra(){
    int d, nod, i, child, cost;
    priority_queue<ii, vector<ii>, greater<ii> >q;
    q.push(ii(0, 1));

    while(!q.empty()){
        d = q.top().first;
        nod  = q.top().second;
        q.pop();

        if(sol[nod] < d)
            continue;

        for(i=0; i<a[nod].size(); i++){
            ///a[nod][j].first = nodul
            ///a[nod][j].second = costul

            child = a[nod][i].first;
            cost = a[nod][i].second;

            if(sol[child] > d + cost){
                sol[child] = d + cost;
                q.push(ii(sol[child], child));
            }
        }
    }
}

int main(){

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d%d%d", &x, &y, &d);
        a[x].push_back(ii(y, d));
    }

    memset(sol, INFINIT, sizeof(sol));
    Daijstra();

    for(i=2; i<=n; i++){
        printf("%d ", sol[i]);
    }
    return 0;
}