#include <fstream>
#include <set>
#include <list>
#include <vector>
#include <utility>

const int NMAX = 5 * 1e4 + 1;
const int MVALUE = 1e5 + 1;

std :: ifstream f("dijkstra.in");
std :: ofstream g("dijkstra.out");

std :: vector < std :: pair <int, int> > Graph[NMAX];
int Nnodes,Nedges;

void Dijkstra (int source);

int main(void){

    int n, m;
    f >> Nnodes;
    f >> Nedges;
    for (int i = 0; i < Nedges; i++ ) {
        int v1, v2, val;
        f >> v1 >> v2 >> val;
        Graph[v1].push_back(std :: make_pair(v2,val));
        Graph[v2].push_back(std :: make_pair(v1,val));
    }
    Dijkstra (1);
}   

void Dijkstra (int source){

    std :: set < std :: pair <int, int > > setDij;

    int dist[Nnodes + 1];
    // int tata[Nnodes + 1];
    for (int i = 0; i <= Nnodes; i ++)
        dist[i] = MVALUE,
        // tata[i] = -1;

    setDij.insert(std :: make_pair(source, 0));

    dist[source] = 0;

    while (!setDij.empty()) {
        
        std :: pair <int, int > temp = *(setDij.begin());
        setDij.erase(setDij.begin());
        int source1 = temp.first;

        for ( auto elem : Graph[source1]){
            int destination = elem.first;
            int value = elem.second;
            if ( dist[destination] > dist[source1] + value)
            {
                if (dist[destination] != MVALUE){
                   setDij.erase(setDij.find(std :: make_pair(destination, dist[destination])));
                }
                dist[destination] = dist[source1] + value;
                setDij.insert(std :: make_pair(destination, dist[destination]));
                // tata[destination] = source1;
            }

        }
    }

    for (int i = 1; i <= Nnodes; i++)
        if ( i != source)
            g << dist[i] << " ";
    // g << "\n Lista de tati " << "\n";
    // for (int i = 1; i <= Nnodes; i++ )
    //     g << tata[i] << " ";
    // g << "\n";
}