#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);
#define tie cin.tie(0);
#define mp make_pair
#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define zeros(x) ( (x ^ (x - 1)) & x )
# define INF 0x3f3f3f3f
    
using namespace std;
 
set < PII > S;
vector < int > D(50100, INF);
vector < PII > V[50100];
int n, m, x, y, cost;
 
void dijkstra(int x)
{
    S.insert(mp(0, x));
    D[x] = 0;
    while (S.size())
    {
        int curr = S.begin()->second;
        S.erase(S.begin());
        for (auto it : V[curr])
        {
            int vertex = it.first;
            int weight = it.second;
            if (D[vertex] > D[curr] + weight)
            {
                if (D[vertex] != INF)
                    S.erase(S.find(mp(D[vertex], vertex)));
                D[vertex] = D[curr] + weight;
                S.insert(mp(D[vertex], vertex));
            }
        }
    }
}
 
int main(){
    IOS tie
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> cost;
        V[x].push_back(mp(y, cost));
    }
    dijkstra(1);
    for (int i = 2; i <= n; i++)
        cout << (D[i] == INF ? 0 : D[i]) << " ";
     
    cerr << "Fucking time elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}