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

using namespace std;

const int nmax = 50000 + 5;
const int inf = INT_MAX;

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

void rezolvare(){
    for (int i = 2; i <= n; i++)
        dist[ i ] = inf;
    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 : vecini[ nod ]){
            if (dist[ v.x ] > cost + v.y ){
                dist[ v.x ] = cost + v.y;
                q.push(make_pair(dist[ v.x ], v.x));
            }
        }
    }
}

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