#include <fstream>
#include <climits>
#include <vector>
#include <queue>

#define cost first
#define vec second

using namespace std;

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

const int nmax = 50005;
const int inf = 100000000;
int n, m, dist[nmax], fr[nmax];
vector< pair<int, int> > v[nmax];
priority_queue< pair<int, int> > H;

int find_Min()
{
    while(!H.empty() && fr[H.top().vec])
        H.pop();

    if(H.empty())
        return -1;

    int aux = H.top().vec; H.pop();
    return aux;
}

void Dijk(int rad)
{
    for(int i = 1; i <= n; i ++)
        if(!dist[i])
            dist[i] = inf;

    dist[rad] = 0;
    H.push(make_pair(0, rad));
    for(int w = 1; w <= n; w ++)
    {
        int nod = find_Min();

        if(nod == -1)
            return;

        fr[nod] = 1;

        for(auto nr : v[nod])
            if(dist[nr.vec] >= dist[nod] + nr.cost)
            {
                dist[nr.vec] = dist[nod] + nr.cost;
                H.push(make_pair(-nr.cost, nr.vec));
            }
    }
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i ++){
        int x, y, c; f >> x >> y >> c;
        v[x].push_back(make_pair(c, y));
    }

    Dijk(1);

    for(int i = 2; i <= n; i ++)
        g << (dist[i] == inf ? -1 : dist[i]) << " ";
    return 0;
}