#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;

const int dim = 50000;
vector<int> d(dim + 1, INT_MAX);

struct cmp {
    bool operator()(int X, int Y) const {
        if (d[X] == d[Y])
            return X < Y;
        return d[X] < d[Y];
    }
};

set<int, cmp> S;
set<int, cmp> ::iterator it;

void Dijkstra(int source, vector<vector<pi>>& edges) {
    S.insert(source);
    d[source] = 0;
    while (!S.empty()) {
        int node = *S.begin();
        S.erase(S.begin());

        for (pi& el : edges[node]) {
            int neigh = el.first;
            int weight = el.second;

            if (d[neigh] > d[node] + weight) {
                d[neigh] = d[node] + weight;

                it = S.find(neigh);
                if (it == S.end())
                    S.insert(neigh);
                else {
                    S.erase(it);
                    S.insert(neigh);
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    f >> n >> m;

    vector<vector<pi>> V(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        f >> a >> b >> c;
        V[a].push_back({ b,c });
    }

    Dijkstra(1, V);

    for (int i = 2; i <= n; i++)
        g << d[i] << ' ';




    return 0;
}