#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N, M;
vector<vector<pair<int, int>>> lisAdiacenta;

vector<int> Dijkstra(const int s)
{
    priority_queue< pair<int, int>, vector <pair<int, int> >> pQueue;
    vector<int> distDij(N + 1, INF);
    vector<bool> apartPQ(N + 1, 0);
    pQueue.push(make_pair(s, 0)), distDij[s] = 0;




    while (!pQueue.empty()) {
        int x = pQueue.top().first;
        pQueue.pop();
        if (!apartPQ[x]) {
            apartPQ[x] = 1;
            for (int i = 1; i < lisAdiacenta[x].size(); i++)
                if (distDij[lisAdiacenta[x][i].first] > distDij[x] + lisAdiacenta[x][i].second) {
                    distDij[lisAdiacenta[x][i].first] = distDij[x] + lisAdiacenta[x][i].second;    ///  update distance
                    pQueue.push(make_pair(lisAdiacenta[x][i].first, distDij[lisAdiacenta[x][i].first]));
                }
        }
    }
    return distDij;
}


int main()
{
    fin>>N>>M;
    int x, y, c;
    vector<pair<int, int>>aux(1,make_pair(-1,-1));
    for(int i = 0; i <= N+1; ++i) {
        lisAdiacenta.push_back(aux);
    }
    for(int i = 1; i <= M; ++i) {
        fin >> x >> y >> c;
        lisAdiacenta[x].push_back(make_pair(y, c));
    }

    vector<int> distDij = Dijkstra(1);

    for(int i = 2; i <= N; i++)
        if(distDij[i] == INF) fout << 0 << " ";
        else fout << distDij[i] << " ";
    return 0;
}