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

using namespace std;

struct Edge {
    int from;
    int to;
    int weight;
    bool operator < (const Edge& b) {
        return this->weight > b.weight;
    }
};

map<int, vector<Edge>> graph;
priority_queue<Edge> q;
map<int, int> dist;

void dijkstra(int s, int n) {
    queue<Edge> q;
    for(int i = 1; i <= n; i++)
        dist[i] = -1;
    q.push({0, s, 0});
    dist[0] = 0;
    while(!q.empty()) {
        Edge top = q.front();
        q.pop();
        if(dist[top.to] == -1) {
            dist[top.to] = top.weight;
            for(Edge next : graph[top.to])
                q.push({next.from, next.to, next.weight+dist[next.from]});
        }
    }
}

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int i, j, n, m, to, from, weight;
    fin>>n>>m;
    for(int i = 0; i < m; i++) {
        fin>>from>>to>>weight;
        graph[from].push_back({from, to, weight});
    }
    dijkstra(1, n);
    for(int i = 2; i <= n; i++) {
        if(dist[i] == -1)
            dist[i] = 0;
        fout<<dist[i]<<" ";
    }
    return 0;
}