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

using namespace std;

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

void dijkstra(int nr_noduri, int nr_muchii, vector <vector <pair <int,int>>> lista_costuri)
{
    int inf = std::numeric_limits<int>::max();
    vector <int> distanta(nr_noduri + 1, inf);
    priority_queue <pair <int, int>> min_heap;

    distanta[1] = 0;
    min_heap.push(make_pair(0, 1));
    while (!min_heap.empty()) {
        int u = min_heap.top().second;
        min_heap.pop();
        for (int i = 0; i < lista_costuri[u].size(); i++) {
            int v = lista_costuri[u][i].first;
            int c = lista_costuri[u][i].second;
            if (distanta[u] + c < distanta[v]) {
                distanta[v] = distanta[u] + c;
                min_heap.push(make_pair(-distanta[v], v));
            }
        }
    }

    for (int i = 2; i <= nr_noduri; i++)
        out << distanta[i] << " ";
}

int main()
{
    int n, m;
    vector <vector <pair <int, int>>> v;
    in >> n >> m;
    v.resize(n + 1);
    for (int i = 0; i < m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        v[x].push_back(make_pair(y,c));
    }
    dijkstra(n,m,v);
    in.close();
    out.close();
    return 0;
}