#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const int NMax = 50000;
int n, m, dist[NMax + 5];

vector<pair<int, int>> G[NMax + 5];

struct PQNode{
    int node, cost;

    PQNode(int n, int c): node(n), cost(c){}
    bool operator < (const PQNode &other) const {
        return cost > other.cost;
    }
};

priority_queue<PQNode> pq;

int main()
{
    int i, u, v, c, node, cost, new_dist, new_node;

    fin>> n >> m;

    for(i = 1; i <= m; ++i){

        fin>> u >> v >> c;
        G[u].push_back({v, c});

    }

    memset(dist, INF, sizeof dist);
    dist[1] = 0;
    pq.emplace(1, 0);

    while(!pq.empty()){
        node = pq.top().node;
        cost = pq.top().cost;
        pq.pop();

        if(cost != dist[node])
            continue;
        for(auto it : G[node]){
            new_dist = cost + it.second;
            new_node = it.first;

            if(new_dist < dist[new_node]){

                dist[new_node] = new_dist;
                pq.emplace(new_node, new_dist);

            }

        }

    }

    for(i = 2; i <= n; ++i){
        if(dist[i] != INF){
            fout<< dist[i] << " ";
        }
        else{
            fout<< 0 << " ";
        }
    }

    return 0;
}