#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#define INF 1e9

using std::cout;
using std::endl;
using std::cin;
using std::vector;
using std::queue;
using std::stack;
using std::fstream;
using std::ios;
using std::setprecision;
using std::fixed;
using std::sort;

struct Nod {
    int y;
    int cost;

    Nod(int y, int cost) {
        this->y = y;
        this->cost = cost;
    }

    bool operator<(const Nod& n) const{
        return this->cost > n.cost;
    }
};

fstream file1("dijkstra.in", ios::in);
fstream file2("dijkstra.out", ios::out);

int nr_noduri, nr_arce;
vector<Nod> graf[50001];
vector<int> dist(50001);
std::priority_queue<Nod> pq;

void form_graf();
void ini_dist();
void dijkstra(int start);
void afis_dist();

int main(int argc, char** argv) {

    file1 >> nr_noduri >> nr_arce;
    ini_dist();
    form_graf();
    dijkstra(1);

    afis_dist();


    file1.close();
    file2.close();
    return 0;
}

void afis_dist() {
    for (int i{ 2 }; i <= nr_noduri; i++) {
        if (dist[i] == INF) {
            file2 << 0 << ' ';
        }
        else {
            file2 << dist[i] << ' ';
        }
    }
}

void dijkstra(int start) {
    dist[start] = 0;
    pq.push({ start, dist[start] });
    while (!pq.empty()) {
        int nod = pq.top().y;
        pq.pop();
        for (auto it = graf[nod].begin(); it != graf[nod].end(); it++) {
            if (dist[(*it).y] > dist[nod] + (*it).cost) {
                pq.push({ (*it).y, dist[(*it).y] });
                dist[(*it).y] = dist[nod] + (*it).cost;
            }
        }
    }
}

void ini_dist() {
    for (int i{ 1 }; i <= nr_noduri; i++) {
        dist[i] = INF;
    }
}

void form_graf() {
    int i, j, k;
    while (file1 >> i >> j >> k) {
        graf[i].push_back({ j, k });
    }
}