#include <bits/stdc++.h>
using namespace std;
#define infinity 1<<30

vector<vector<pair<int, int> > > graph;
vector<bool> inQueue;
vector<int> dist;
int n, m;

struct compDist{
    bool operator()(int x, int y){
        return dist[x]>dist[y];
    }
};

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

void dijksta(){
    dist.at(1) = 0;
    Queue.push(1);
    inQueue.at(1) = true;

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

        for(auto& elem:graph.at(currentNode)){
            if(dist.at(currentNode)+elem.second < dist.at(elem.first)){
                dist.at(elem.first) = dist.at(currentNode)+elem.second;
                if(!inQueue.at(elem.first)){
                    Queue.push(elem.first);
                    inQueue.at(elem.first) = true;
                }
            }
        }
    }
}


//rff = read from file
void rff(){
    ifstream fin("dijkstra.in");

    fin>>n>>m;

    graph.resize(n+1, vector<pair<int, int> >());
    inQueue.resize(n+1, false);
    dist.resize(n+1, infinity);

    int x, y, c;

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

    return;
}

//pif = print in file
void pif(){
    ofstream fout("dijkstra.out");
    for(int i=2; i<=n; i++)
        if(dist.at(i)==infinity) fout<<0<<" ";
        else fout<<dist.at(i)<<" ";

    return;
}


int main()
{
    rff();
    dijksta();
    pif();
}