#include <bits/stdc++.h>

using namespace std;
#define NMAX 50001
#define infinity 1000000000

vector<int> dist(NMAX, infinity);
vector<bool> inQueue(NMAX, false);
vector<vector<pair<int, int>>> graph(NMAX);
int n, m;

struct comp{
    bool operator()(int a, int b){
        return dist.at(a) > dist.at(b);
    }
};

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

void readFromFile(){
    ifstream fin("dijkstra.in");
    fin>>n>>m;
    int x, y, c;
    for(int i=1; i<=m; i++){
        fin>>x>>y>>c;
        graph.at(x).push_back(make_pair(y, c));
    }
    fin.close();
}

void dijkstra(){
    Queue.push(1);
    dist.at(1) = 0;
    int current;
    while(!Queue.empty()){
        current = Queue.top();
        Queue.pop();
        inQueue.at(current) = false;

        for(auto& elem:graph.at(current)){
            if(dist.at(current) + elem.second < dist.at(elem.first)){
                dist.at(elem.first) = dist.at(current) + elem.second;

                if(!inQueue.at(elem.first)){
                    Queue.push(elem.first);
                    inQueue.at(elem.first) = true;
                }
            }
        }
    }
}

void print(){
    ofstream fout("dijkstra.out");

    for(int i=2; i<=n; i++)
        if(dist.at(i)==infinity) fout<<0<<" ";
        else fout<<dist.at(i)<<" ";

    fout.close();
}

int main()
{
    readFromFile();
    dijkstra();
    print();
}