#include <bits/stdc++.h>

#define DIM 50000
#define INF INT_MAX
#define pii pair<int,int>

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){

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

    q.push({0,start});

    while(!q.empty()){

        int nod = q.top().second;
        int c = q.top().first;

        q.pop();

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

        for(auto i : L[nod]){
            int vec = i.first;
            int cc = i.second;

            if(d[vec] > d[nod] + cc){
                d[vec] = d[nod] + cc;
                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});
    }

    dijkstra(1);

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

    return 0;
}