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

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

bool inQ[50005];
vector<pair<int, int> > graph[50005];
int n, m, dist[50005];

struct comparator{
    bool operator() (int x, int y){
        return x<y;
    }
};

priority_queue<int,vector<int >,comparator> Q;


void citire() {
    f >> n >> m;
    for (int i = 1; i <= n; i++)
        dist[i] = INT_MAX / 2 - 1;
    dist[1] = 0;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        f >> x >> y >> c;
        graph[x].emplace_back(y, c);
    }
}

void rezolvare() {
    Q.push(1);
    inQ[1] = 1;
    while (!Q.empty()) {
        int nod = Q.top();
        inQ[nod]=1;
        Q.pop();
        for (auto &v:graph[nod]) {
            if (dist[v.first] > dist[nod] + v.second) {
                dist[v.first] = dist[nod] + v.second;
                if(!inQ[v.first]){
                    Q.push(v.first);
                    inQ[v.first]=1;
                }

            }
        }
    }

    for(int i=2; i<=n; i++){
        if(INT_MAX / 2 - 1==dist[i])
            g<<0<<" ";
        else
            g<<dist[i]<<" ";
    }
}

int main() {
    citire();
    rezolvare();
    return 0;
}