#include <fstream>
#include <iostream>
#include <queue>
#include <utility>

#define pp pair<int,int>

using namespace std;

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

const int MaxN = 50001;
const int INF = 1 << 30;

vector < pair < int , int > > G[MaxN];// pair.first este nodu pair.second este costul pana la nod
int d[MaxN],n,m;//distante

int main()
{
    int x,y,c;

    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        f >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
        G[y].push_back(make_pair(x,c));
    }


    int source = 1;

    priority_queue < pp, vector < pp > ,greater< pp > > pq; //primu parametru tipu de date; al doilea structura pe care se face pq - ul; al 3 - lea pastrea prop de MIN heap

    for(int i = 2;i <= n; i++) d[i] = INF;// setez distantele pana la INF
    d[source] = 0;//distanta din sursa e 0

    pq.push(make_pair(source,d[source]));// bag sursa si distana in heap

    while(!pq.empty())//cat mai e ceva in heap
    {
        pair <int,int> curent = pq.top();//iau min-ul din heap
        pq.pop();//eimin min-ul

        int node = curent.first;//nodu de la care relaxez
        int distNode = curent.second;//distanta pana la nodul de la care relaxez

        if(distNode <= d[node])//comparatia garanteaza ca verificam fiecare nod doar odata si le ingnoram pe celelalte din heap deoarece ele vor avea valori mai mari
        {

            for(vector<pp>::iterator i = G[node].begin(); i != G[node].end(); ++i)//iteram prin toti vecinii
            {
                int newNode = i -> first;
                int newDistNode = i -> second;
                if(d[newNode] > d[node] + newDistNode)//daca putem relaxa
                {
                    d[newNode] = d[node] + newDistNode;
                    pq.push(make_pair(newNode,d[newNode]));//bagam in coada
                }
            }

        }
    }

    for(int i = 1; i <= n; i++)
    {
        if(i != source)
        {
            if(d[i] == INF) d[i] = 0;
            g << d[i] << " ";
        }
    }

    return 0;
}