#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);
//     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);
//                 }
//             }
//         }
//     }

//     for(unsigned int i = 0; i < dist.size(); ++i){
//         if(dist[i] == 100000000){
//             dist[i] = 0;
//         }
//     }

//     return dist;
// }

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);
    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(auto i: g[u]){
            if(!visited[i.x]){
                if(dist[i.x] > dist[u] + i.cost){
                   dist[i.x] = dist[u] + i.cost;
                   Node new_node;
                   new_node.x = i.x;
                   new_node.cost = dist[i.x];
                   pq.push(new_node);
                }
            }
        }
    }

    for(auto &i: dist){
        if(i == 100000000){
            i = 0;
        }
    }

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