#include <fstream>
#include <vector>
#include <queue>
#define INF 1<<30
#define MAX 50010

using namespace std;

struct data{
    int weight, node;
} nd;

int n, m, dist[MAX];
vector <data> v[MAX];
priority_queue< pair<int, int> > q;

void read();
void dijktra();
void write();

int main(){
    read();
    dijktra();
    write();
    return 0;
}

void read(){
    ifstream fin ("dijkstra.in");
    fin >> n >> m;
    q.push(make_pair(0, 1));
    for (int i = 0; i < m; ++i){
        int x, y, c;
        fin >> x >> y >> c;
        nd.weight = c, nd.node = y;
        v[x].push_back(nd);
    }
    for (int i = 2; i <= n; ++i)
        dist[i] = INF;
    fin.close();
}

void dijktra(){
    while (!q.empty()){
        int k = q.top().second;
        int c = -q.top().first;
        q.pop();

        for (unsigned int i = 0; i < v[k].size(); ++i)
            if (dist[v[k][i].node] > c+v[k][i].weight)
                dist[v[k][i].node] = c + v[k][i].weight,
                q.push(make_pair(-dist[v[k][i].node], v[k][i].node));
    }
}

void write(){
    ofstream fout ("dijkstra.out");
    for (int i = 2; i <= n; ++i)
        fout << (dist[i] == INF ? 0 : dist[i]) << " ";
    fout << "\n";
    fout.close();
}