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

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

struct nd {
    int node;
    int distance;
};

int n, m, x, y, cost;

vector<int> dijkstra(vector<vector<pair<int, int>>>& list, int start) {
    
    struct compareFuncPairMin {
        bool operator()(nd a, nd  b) const {
            return a.distance > b.distance;
        }
    };

    priority_queue<nd, vector<nd>, compareFuncPairMin> heap;
    vector<int> dist(n + 1, -1);
    vector<int> parent(n + 1, 0);
    vector<int> visited(n + 1, 0);
 
    dist[start] = 0;
    heap.push({start,dist[start]});
    
    while (!heap.empty()) {
        nd current = heap.top();
        heap.pop();
        if (visited[current.node] == 0) {
            visited[current.node] = 1;
            for (auto& e : list[current.node]) {
                if (dist[e.first] == -1 || current.distance + e.second < dist[e.first]) {
                    dist[e.first] = current.distance + e.second;
                    parent[e.first] = current.node;
                    heap.push({ e.first,dist[e.first] });
                }
            }
        }
    }
    return dist;
}


int main()
{
    int start = 1;
    cin >> n >> m;
    vector<vector<pair<int, int>>> list(n+1);

    for (int i = 0; i < m; i++) {
        cin >> x >> y >> cost;
        list[x].push_back({ y,cost });
    }

    vector<int> dist = dijkstra(list, start);

    for (int i = 2; i < dist.size(); i++) {
        if (dist[i] == -1) { dist[i] = 0; }
        cout << dist[i] << " ";
    }

}