#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;
    }
};

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);
vector<int> noduri;

void form_graf();
void ini_dist();
int dist_min();
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;
    noduri.push_back(start);
    while (!noduri.empty()) {
        int pos = dist_min();
        int nod = noduri[pos];
        noduri.erase(noduri.begin() + pos);
        for (auto it = graf[nod].begin(); it != graf[nod].end(); it++) {
            if (dist[(*it).y] > dist[nod] + (*it).cost) {
                noduri.push_back((*it).y);
                dist[(*it).y] = dist[nod] + (*it).cost;
            }
        }
    }
}

int dist_min() {
    int min = dist[noduri[0]], pos{ 0 };
    for (int i{ 1 }; i < noduri.size(); i++) {
        if (min > dist[noduri[i]]) {
            min = dist[noduri[i]];
            pos = i;
        }
    }
    return pos;
}

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 });
    }
}