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

using namespace std;

struct Node{
    int x, cost;
};

struct Compare {
    bool operator()(Node const& p1, Node const& p2)
    {
        return p1.cost > p2.cost;
    }
};


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

    while(!pq.empty()){
        int u = pq.top().x;
        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;
                   Node new_node;
                   new_node.x = g[u][i].x;
                   new_node.cost = dist[g[u][i].x];
                   pq.push(new_node);
                }
            }
        }
    }

    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;
}