#include <iostream>
#include <fstream>
#include <queue>
#include <list>
#include <vector>

using namespace std;

#define INFINITY 99999999
#define MAX_N 50001

int n,m;
list<pair<int,int>> *links;

void addLink(int origin,int destination, int weight)
{
    links[origin].push_back(make_pair(weight,destination));
    //links[destination].push_back(make_pair(weight,origin));
}

vector<int> dist;

void Dijkstra(int source)
{
    priority_queue< pair<int,int>,
                    vector< pair<int,int> >,
                    greater< pair<int,int> >
                    > pq;
    pq.push(make_pair(0, source));


    dist[source] = 0;
    while(!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        for(auto it = links[u].begin(); it != links[u].end(); it++)
        {
            int v = (*it).second;
            int weight = (*it).first;
            if( dist[v] > dist[u] + weight )
            {
                //if( v == destination)
                //{
                //    return dist[u] + weight;
                //}
                //else
                //{
                    dist[v] = dist[u] + weight;
                    pq.push(make_pair(dist[v],v));
                //}
            }
        }
    }
}

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    // read
    f>>n;
    links = new list< pair<int,int> >[n];
    dist.resize(n,INFINITY);
    f>>m;

    for(int i = 0; i < m; i++)
    {
        int o,d,w;
        f>>o;
        f>>d;
        f>>w;
        addLink(o-1,d-1,w);
    }

    Dijkstra(0);

    for(int i = 1; i < n; i++)
    {
        if(dist[i] == INFINITY)
        {
            g<<0<<" ";
        }
        else
        {
            g<<dist[i]<<" ";
        }
    }
}