#include <bits/stdc++.h>
using namespace std;

#define N_MAX 50000 + 1

vector<vector<pair<int, int> > > graph(N_MAX, vector<pair<int, int> > (0));
vector<int> d(N_MAX, INT_MAX);
vector<bool> inQueue(N_MAX, false);

struct compare{
    bool operator()(int x, int y){
        return d.at(x) > d.at(y);
    }
};

priority_queue<int, vector<int>, compare> Queue;

void dijkstra(int startNode){
    d.at(startNode) = 0;
    Queue.push(startNode);
    inQueue.at(startNode) = true;

    int currentNode;
    while(!Queue.empty()){
        currentNode = Queue.top();
        Queue.pop();
        inQueue.at(currentNode) = false;

        for(auto& node:graph.at(currentNode)){
            if(d.at(currentNode) + node.second < d.at(node.first)){
                d.at(node.first) = d.at(currentNode) + node.second;

                if(inQueue.at(node.first)==false){
                    Queue.push(node.first);
                    inQueue.at(node.first)=true;
            }
        }
    }
}
}

int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int n, m;
    fin>>n>>m;

    int x, y, c;

    for(auto i=1; i<=m; i++){
        fin>>x>>y>>c;
        graph.at(x).push_back(make_pair(y, c));
    }

    dijkstra(1);

    for(auto i=2; i<=n; i++) fout<<(d.at(i)==INT_MAX? 0:d.at(i))<<" ";
}