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

using namespace std;

struct Node{
    int x, cost;
};

vector<int> dijkstra(vector<vector<Node> > g){
    priority_queue<int, vector<int>, greater<int> > pq;
    pq.push(0);
    vector<bool> visited(g.size(), false);
    vector<int> dist(g.size(), 100000000);
    dist[0] = 0;

    while(!pq.empty()){
        int u = pq.top();
        pq.pop();
        visited[u] = true;
        for(unsigned int i = 0; i < g[u].size(); ++i){
            if(!visited[g[u][i].x]){
                if(dist[g[u][i].x] > dist[u] + g[u][i].cost){
                   dist[g[u][i].x] = dist[u] + g[u][i].cost;
                   pq.push(g[u][i].x);
                }
            }
        }
    }

    return dist;
}

int main(){

    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int N, M;
    fin >> N >> M;

    vector<vector<Node> > graph(N, vector<Node>());
    for(int i = 0; i < M; ++i){
        int x, y, c;
        fin >> x >> y >> c;
        Node g;
        g.x = y - 1;
        g.cost = c;
        graph[x - 1].push_back(g);
    }

    vector<int> ans = dijkstra(graph);
    for(unsigned int i = 1; i < ans.size(); ++i){
        fout << ans[i] << " ";
    }


    return 0;
}