#include <iostream>
#include <bits/stdc++.h>

#define G_max 50005
using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

struct point
{
    int nod;
    int d;
};

bool operator<(point a, point b)
{
    return a.d > b.d;
}
vector<pair <int,int> > G[G_max];
priority_queue < point > pq;

int dist[G_max];
int main()
{
    int N,M,x,y,z;
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        f>>x>>y>>z;
        G[x].push_back(make_pair(y,z));
    }


/*
   for(int k=0;k<N;k++)
    for(int i=0;i<G[k].size();i++)
    {
        g<<G[k][i].first<<' '<<G[k][i].second<<'\n';
    }
*/
    memset(dist,0x3f, sizeof(dist));
    pq.push({1,0});

    while(!pq.empty())
    {
        int nod = pq.top().nod;
        int d = pq.top().d;
        pq.pop();

        if(dist[nod] != 0x3f3f3f3f)
            continue;
        dist[nod] = d;

        for(int i=0; i<G[nod].size();i++)
        pq.push({G[nod][i].first, d + G[nod][i].second});
    }

    for(int i=2;i<=N; i++)
        if(dist[i]== 0x3f3f3f3f)
            g<<-1<<' ';
        else
            g<<dist[i]<<' ';


    return 0;
}