#include <bits/stdc++.h>

#define pii pair<int,int>

#define DIM 50000
#define INF INT_MAX

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m;
int x,y,c;

int d[DIM+5];

vector <pii> L[DIM+5];

priority_queue<pii,vector<pii>,greater<pii>> q;

void dijkstra(int start){

    q.push({0,start});

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

        if(d[nod] != val){
            continue;
        }

        for(int i = 0;i<L[nod].size();i++){
            int vec = L[nod][i].first;
            int c = L[nod][i].second;

            if(d[vec] > d[nod]+c){
                d[vec] = d[nod]+c;
                q.push({d[vec],vec});
            }
        }
    }

}

int main(){
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>x>>y>>c;

        L[x].push_back({y,c});
    }

    d[1] = 0;
    for(int i=2;i<=n;i++){
        d[i] = INF;
    }

    dijkstra(1);

    for(int i=2;i<=n;i++){
        g<<d[i]<<" ";
    }
    return 0;
}