#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define INF 999999999
#define N 50000

using namespace std;

struct comparator {
    bool operator()(pair<int, int> &pair1, pair<int, int> &pair2) {
        return pair1.second > pair2.second;  
    }
};

int d[N];
vector<pair<int, int> > adj[N];
priority_queue<pair<int, int>, vector<pair<int, int> >, comparator> q;

int main() {
    int n, m, i;

    ifstream in("dijkstra.in");
    in >> n >> m;

    for (i = 0; i < m; i++) {
        int start, end, cost;
        in >> start >> end >> cost;
        adj[start].push_back(make_pair(end, cost));
    }

    in.close();
    ofstream out("dijkstra.out");

    d[1] = 0;

    for (int i = 2 ; i <= n ; i++) {
        d[i] = INF;
    }
     
    q.push(make_pair(1, 0));

    while(!q.empty()) {
        pair<int, int> currentNode = q.top();
        q.pop();

        if (d[currentNode.first] < currentNode.second) {
            continue;
        }
         
        for (pair<int, int> node : adj[currentNode.first]) {
            if (d[currentNode.first] + node.second < d[node.first]) {
                d[node.first] = d[currentNode.first] + node.second;
                q.push(make_pair(node.first, d[node.first]));
            }
        }

    }
     
    for (i = 2 ; i <= n ; i++) {
        if (d[i] == INF) {
            out << 0 << " ";
        } else {
            out << d[i] << " ";
        }
    }


    out << endl;
    out.close();

    return 0;
}