#include <bits/stdc++.h>
#define NMAX 50001
#define MMAX 250001
#define infinity 2000000000
using namespace std;

typedef unsigned int uint;
typedef unsigned short ushort;

struct comp{
    bool operator()(uint a, uint b){
        return a>b;
    }
};

vector<vector<pair<uint, ushort>>> graph(MMAX);
vector<uint> dist(NMAX);
priority_queue<uint, vector<uint>, comp> pQueue;
vector<bool> inQueue(NMAX, false);
uint N, M;

void readFromFile(){

    ifstream fin("dijkstra.in");

    fin>>N>>M;
    {
        uint x, y;
        ushort c;

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

    }

    fin.close();
}

void print(){

    ofstream fout("dijkstra.out");

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

    fout.close();
}

void findMinimumPath(uint startNode){

    for(uint i=1; i<=N; i++) dist.at(i) = infinity;

    dist.at(startNode) = 0;
    pQueue.push(startNode);
    inQueue.at(startNode) = true;

    uint currentNode;

    while(!pQueue.empty()){
        currentNode = pQueue.top();
        pQueue.pop();
        inQueue.at(currentNode) = 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)){
                pQueue.push(elem.first);
                inQueue.at(elem.first) = true;
            }
        }

    }
}

int main()
{
    readFromFile();
    findMinimumPath(1);
    print();
}