#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct muchie{
    int dest, cost;
    muchie(const int a, const int b): dest(a), cost(b){}
};

bool operator<(const muchie& a, const muchie& b){
    return a.cost > b.cost || (a.cost == b.cost && a.dest < b.dest);
}

void dijkstra(const int surs, const vector<vector<muchie>>& vec,
    vector<int>& dist){

    fill(dist.begin(), dist.end(), 1000000000);

    dist[surs] = 0;
    priority_queue<muchie> pq;
    pq.push(muchie(surs, 0));

    while(!pq.empty()){
        const int cur = pq.top().dest, d_cur = pq.top().cost;
        pq.pop();
        if(dist[cur] != d_cur){
            continue;
        }
        for(int i = 0; i < vec[cur].size(); ++i){
            if(dist[vec[cur][i].dest] > d_cur + vec[cur][i].cost){
                dist[vec[cur][i].dest] = d_cur + vec[cur][i].cost;
                pq.push(muchie(vec[cur][i].dest, dist[vec[cur][i].dest]));
            }
        }
    }
}

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

    int n, m;
    f >> n >> m;

    vector<vector<muchie> > vec(n);

    for(int i = 0, a, b, c; i < m; ++i){
        f >> a >> b >> c;
        --a, --b;
        vec[a].push_back(muchie(b, c));
    }

    vector<int> dist(n);

    dijkstra(0, vec, dist);
    for(int i = 1; i < n; ++i){
        g << (dist[i] == 1000000000 ? 0 : dist[i]) << ' ';
    }
    return 0;
}