#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4 + 4;
int dist[NMAX], n, m;
vector < pair <int, int> > g[NMAX];

class ComparePQ {
public:
    bool operator()(pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    }
};

void setup() {
    int i;
    for(i = 0; i < NMAX; ++i) dist[i] = INT_MAX;
}

void dijkstra(int startingNode) {
    setup();
    priority_queue <pair<int, int>, vector <pair <int, int> >, ComparePQ> q;

    q.push({startingNode, 0});

    pair <int, int> head;

    while(!q.empty()) {
        head = q.top();
        q.pop();

        if(dist[head.first] <= head.second) continue;

        dist[head.first] = head.second;

        for(auto &it : g[head.first]) {
            if(dist[it.first] > dist[head.first] + it.second) {
               q.push({it.first, dist[head.first] + it.second});
            }

        }
    }
}

int main(){
    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back({b, c});
    }

    dijkstra(1);

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

    return 0;
}