#include <iostream>
#include <stdio.h>
#include <fstream>
#include <vector>
#include <queue>

#define DIM 50002
#define inf 300000

using std::ifstream;
using std::ofstream;
using std::vector;
using std::priority_queue;

ifstream f("dijkstra.in");


class Node {
public:
    int y, cost;
    Node(int y, int cost): y{y},cost{cost}{}
};

void read(int &n, int& m, vector<Node> G[]) {

    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, cost;
        f >> x >> y >> cost;
        G[x].push_back(Node(y,cost));
    }
    f.close();
}

int main()
{
    vector<Node> G[DIM];
    int n,m,i;
    read(n,m,G);
    int d[DIM];
    for(i=1;i<=n;i++){
        d[i]=inf;
    }
    d[1]=0;
    auto cmp=[&](int x, int y){return d[x]>d[y];};
    priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
    pq.push(1);
    while(!pq.empty()){
        int x=pq.top();
        pq.pop();
        for(auto y:G[x]){
            if(d[y.y]>d[x]+y.cost){
                d[y.y]=d[x]+y.cost;
                pq.push(y.y);
            }
        }
    }
    ofstream g("dijkstra.out");
    for(i=2;i<=n;i++){
        if(d[i]==inf){
            g<<0<<" ";
        }
        else
            g<<d[i]<<" ";
    }
    g.close();
    return 0;
}