#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4 + 2;
const int INF = INT_MAX;

int n, m, dist[NMAX];
vector<pair<int, int>> v[NMAX];
int main()
{
    memset(dist, -1, sizeof(dist));
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        fin >> x >> y >> z;
        v[x].push_back({y, z});
    }
    for (int i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }

    set<pair<int, int>> st;
    st.insert({0, 1});
    dist[1] = 0;
    while (!st.empty())
    {
        int nod = (st.begin()->second);
        st.erase(st.begin());
        for (auto [vecin, cost] : v[nod])
        {
            if (dist[vecin] > dist[nod] + cost)
            {
                st.erase({dist[vecin], vecin});
                dist[vecin] = dist[nod] + cost;
                st.insert({dist[vecin], vecin});
            }
        }
    }
    for (int i = 2; i <= n; i++)
    {
        fout << (dist[i] == INF ? 0 : dist[i]) << " ";
    }
    return 0;
}