//https://infoarena.ro/problema/dijkstra

#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector <pair<int, int>> neighbor[50005];
priority_queue <pair<int, int>> findMinDistance;
int distanceNode[50005];

void dijkstra(int node, int nodesNo) {
    distanceNode[node] = 0;
    findMinDistance.push({node, distanceNode[node]});

    while (!findMinDistance.empty()) {
        int currentNode = findMinDistance.top().first;
        findMinDistance.pop();
        for (int i = 0; i < neighbor[currentNode].size(); ++i) {
            if (distanceNode[neighbor[currentNode][i].first] <= distanceNode[currentNode] + neighbor[currentNode][i].second) continue;
            distanceNode[neighbor[currentNode][i].first] = distanceNode[currentNode] + neighbor[currentNode][i].second;
            findMinDistance.push({neighbor[currentNode][i].first, distanceNode[neighbor[currentNode][i].first]});
        }
    }
    for (int i = 2; i <= nodesNo; ++i) {
        fout << distanceNode[i] << " ";
    }
}

int main()
{
    int nodesNo, edgesNo;

    fin >> nodesNo >> edgesNo;

    for (int i = 1; i <= edgesNo; ++i) {
        distanceNode[i] = 100000000;
    }

    for (int i = 1; i <= edgesNo; ++i) {
        int xNode, yNode, distanceXToY;
        fin >> xNode >> yNode >> distanceXToY;
        neighbor[xNode].push_back({yNode, distanceXToY});
    }

    dijkstra(1, nodesNo);
}