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

using namespace std;

#define INFINITY 99999999
#define MAX_N 50001
#define IPair pair<int,int>

int n,m;
list<IPair> *links;
int *visit;
void addLink(int origin,int destination, int weight)
{
    links[origin].push_back(make_pair(weight,destination));
    //links[destination].push_back(make_pair(weight,origin));
}

int *dist;

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


    dist[source] = 0;
    while(!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if(visit[u] == 1)
        {
            continue;
        }
        visit[u] = 1;
        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 )
            {
                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< IPair >[n];

    dist = new int[n]();
    visit= new int[n]();
    for(int i = 0; i <n; i++)
    {
        dist[i] = INFINITY;
        visit[i] = 0;
    }

    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/4; i++)
    {
        if(dist[i] == INFINITY)
        {
            g<<0<<" ";
        }
        else
        {
            g<<dist[i]<<" ";
        }
    }
}