#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

void Bellman_Ford(int source, int noNodes, vector<vector<pair<int,int> > > &graph) {

    queue<int> Q;
    vector<int> distanta(noNodes+1, 1e9);
    Q.push(source);
    distanta[source] = 0;

    while(!Q.empty()) {

        int node = Q.front();
        Q.pop();

        for(auto neighbor : graph[node]) {

            int weight = neighbor.first;
            int newNode = neighbor.second;

            if(distanta[node] + weight < distanta[newNode]) {
                distanta[newNode] = distanta[node] + weight;
                Q.push(newNode);
            }
        }
    }

    for(int i=2; i<=noNodes; i++)
        fout << distanta[i] << ' ';

}

int main() {

    int noNodes, noEdges;
    fin >> noNodes >> noEdges;

   vector<vector<pair<int,int> > > graph(noNodes+1, vector<pair<int,int> >());

    for(int i=1; i<=noNodes; i++) {
        int firstNode, secondNode, weight;
        fin >> firstNode >> secondNode >> weight;

        graph[firstNode].push_back({weight, secondNode});
    }

    Bellman_Ford(1, noNodes, graph);

    return 0;
}