#include <bits/stdc++.h>
#define nmax 50005
#define x first
#define y second
#define pp pair <int, int>

using namespace std;

vector < pp > vec[ nmax ];
priority_queue <pp, vector < pp >, greater< pp > > q;
int n, m;
int dist[ nmax ];

void rezolvare();

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> n >> m;
    for (int i = 1, xx, yy, val; i <= n; i++){
        cin >> xx >> yy >> val;
        vec[ xx ].push_back(make_pair(yy, val));
    }
    rezolvare();
    for (int i = 2; i <= n; i++)
        cout << (dist[ i ] == nmax ? 0 : dist[ i ]) << " ";
}

void rezolvare(){
    for (int i = 2; i <= n; i++)
        dist[ i ] = nmax / 2;
    q.push(make_pair(0, 1));
    while (q.empty() == false){
        int nod = q.top().y;
        int cost = q.top().x;
        q.pop();
        if (cost > dist[ nod ])
            continue;
        for (auto v : vec[ nod ]){
            if (dist[ v.x ] > cost + v.y ){
                dist[ v.x ] = cost + v.y;
                q.push(make_pair(dist[ v.x ], v.x));
            }
        }
    }
}