#include <fstream>
#include <set>
#include <vector>
#define infinit 1e9

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

const int N = 5e4;
int n, m, radacina, cm[N + 1];
vector <pair<int, int>> G[N + 1];

void dijkstra(int sursa)
{
    for(int i = 1; i <= N; i++)
        cm[i] = infinit;

    cm[sursa] = 0;
    set <pair<int, int>> S;
    S.insert({0, sursa});

    while(!S.empty()){
        int pivot = S.begin()->second;
        for(auto indice : G[pivot]){
            int cost_initial = cm[indice.first], cost_nou = cm[pivot] + indice.second;

            if (cm[indice.first] != infinit) /// era deja in s
                S.erase({cm[indice.first], indice.first});

            cm[indice.first] = min(cost_nou, cost_initial);
            S.insert({cm[indice.first], indice.first});
        }

        S.erase(S.begin());
    }
}

int main()
{
    cin >> n >> m;
    radacina = 1;
    for(int k = 1; k <= m; k++){
        int i, j, c;
        cin >> i >> j >> c;
        G[i].push_back({j, c});
    }

    dijkstra(radacina);
    for(int i = 1; i <= n; i++)
        if (i != radacina)
            cout << cm[i] << " ";

    return 0;
}