#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5 * 1e4 + 15;
const int INF = 1e8;

struct edge{

    int dest, cost;
    bool operator < (const edge &aux) const{
        return cost > aux.cost;
    }

};

int dist[MAXN];
priority_queue <edge> pq;
vector <edge> g[MAXN];

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


int main(){

    int n, m; fin >> n >> m;
    for(int i = 1; i <= m ; ++i){
        int x, y, cost; fin >> x >> y >> cost;
        g[x].push_back({y, cost});
    }

    for(int i = 1; i <= n; ++i) dist[i] = INF;

    pq.push({1, 0});
    while(pq.size()){

        edge x = pq.top();
        pq.pop();

        if(dist[x.dest] == INF){
            dist[x.dest] = x.cost;

            for(auto y : g[x.dest]){
                if(dist[y.dest] == INF )
                    pq.push({y.dest, dist[x.dest] + y.cost});
            }
        }
    }

    for(int i = 2 ; i <= n; ++i)
        fout << dist[i] << ' ' ;
    return 0;
}