#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4 + 2;

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});
    }
    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] == -1)
            {
                dist[vecin] = dist[nod] + cost;
                st.insert({dist[vecin], vecin});
            }
        }
    }
    for(int i = 2; i <= n; i++)
    {
        fout << dist[i] << " ";
    }
    return 0;
}