#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
//#define f cin
//#define g cout
set<pair<long long, int>> s;
vector<vector<pair<int, int>>> v;
vector<long long> d;
int n;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);
    int m;
    f >> n >> m;
    v.resize(n + 1);
    for (int a, b, c; m; m--)
        f >> a >> b >> c, v[a].push_back({b, c});
    d.assign(n + 1, LLONG_MAX);
    d[1] = 0;
    s.insert({0, 1});
    while (!s.empty())
    {
        int ac = s.begin()->second;
        s.erase(s.begin());
        for (auto &i : v[ac])
        {
            int to = i.first;
            long long dis = i.second;
            if (d[ac] + dis < d[to])
            {
                s.erase({d[to], to});
                d[to] = d[ac] + dis;
                s.insert({d[to], to});
            }
        }
    }
    for (int i = 2; i <= n; i++)
        g << d[i] << " ";
    return 0;
}