#include <fstream>
#include <vector>
#include <cstring>
#include <set>

#define pair pair<int, int>

using namespace std;


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

const int inf = 0x3f3f3f3f;
const int NM = 50005;

vector <pair> G[NM];
multiset <pair> H;
pair crt;

int N, E, edge, from, to, cost, i, node;
bool visited[NM];
int D[NM];

int main()
{
    in >> N >> E;
    for (edge = 1; edge <= E; ++edge) {
        in >> from >> to >> cost;
        G[from].push_back({cost, to});
    }

    memset(D, inf, sizeof(D));
    D[1] = 0; H.insert({0, 1});   // cost, node

    while (!H.empty()) {
        crt = *(H.begin());
        cost = crt.first;
        node = crt.second;
        H.erase(H.begin());

        visited[node] = 1;

        for (auto &it: G[node]) {
            if (!visited[it.second] && it.first + cost < D[it.second]) {
                if (D[it.second] != inf) {
                    H.erase(H.find({D[it.first], it.second}));
                }
                D[it.second] = it.first + cost;
                H.insert({D[it.second], it.second});
            }
        }
    }

    for (i = 2; i <= N; ++i) {
        if (D[i] == inf)
            out << "0 ";
        else
            out << D[i] << ' ';
    }


    return 0;
}