#include <bits/stdc++.h>

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

const int INF = 1e9;

std::vector<std::pair<int, int>> nei[50001];
std::priority_queue<std::pair<int, int>> q;
int n, m, d[50001];
bool viz[50001];

void dijkstra(int start){
    int i, cost, node, next_node;
    q.push({0, start});
    viz[start] = 1;
    for(i = 1; i <= n; i++)
        if(i != start)
            d[i] = INF;
    while(!q.empty()){
        node = q.top().second;
        q.pop();
        viz[node] = 0;
        for(i = 0; i < nei[node].size(); i++){
            next_node = nei[node][i].second;
            cost = nei[node][i].first;
            if(d[next_node] > d[node] + cost){
                d[next_node] = d[node] + cost;
                if(!viz[next_node]){
                    viz[next_node] = 1;
                    q.push({-d[next_node], next_node});   //bagam cu - deoarece vrem minimul, nu maximul
                }
            }
        }
    }
}


int main()
{
    int i, x, y, cost, start = 1;
    fin >> n >> m;
    for(i = 0; i < m; i++){
        fin >> x >> y >> cost;
        nei[x].push_back(std::make_pair(cost, y));
    }
    dijkstra(start);

    for(int i = 1; i <= n; ++i)
        if(i != start){
            if(d[i] == INF)
                fout << 0 <<' ';
            else
                fout << d[i] << " ";
        }

    return 0;
}