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

using namespace std;

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

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

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

    cm[sursa] = 0;
    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 (cost_nou < cost_initial){ ///modificam costul minim
                if (cost_initial != infinit) /// e deja in s
                    S.erase({cm[indice.first], indice.first});

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

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

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

    dijkstra(1);
    for(int i = 2; i <= n; i++){
        if (cm[i] < infinit)
            cout << cm[i] << " ";

        else
            cout << 0 << " ";
    }

    return 0;
}