#include <bits/stdc++.h>

using namespace std;

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

#define dist first
#define poz second

vector <pair < int, int > > adj[50001];
priority_queue <pair < int, int > > pq;

int dist[50001];

int main()
{
    int n, m;
    f >> n >> m;
    for ( int i = 1; i <= n; i ++ )
    {
        int x, y, z;
        f >> x >> y >> z;
        adj[x].push_back( {z, y} );
    }
    dist[1] = 1;
    pq.push( { 1, 1 } );
    while ( pq.size() )
    {
        pair < int, int > c = pq.top();
        pq.pop();
        if ( c.dist <= dist[c.poz] )
        {
            for ( int i = 0; i < adj[c.poz].size(); i ++ )
            {
                pair <int, int> l = adj[c.poz][i];
                if ( dist[l.poz] == 0 || c.dist + l.dist < dist[l.poz] )
                {
                    dist[l.poz] = c.dist + l.dist;
                    pq.push( { c.dist + l.dist, l.poz } );
                }
            }
        }
    }
    for ( int i = 2; i <= n; i ++ )
        g << dist[i] - 1 << " ";
    return 0;
}