#include <iostream>
#include <vector>
#include <fstream>

#define NMAX 50005
#define INF 30000

using namespace std;

int dist[NMAX];
int vizitat[NMAX];
vector<int> cost[NMAX];
vector<int> graph[NMAX];

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int N, M;
    f>>N>>M;
    //cout<<N;
    int x, y, c;
    for(int i = 1; i <= M; i++)
    {
        f>>x>>y>>c;
        graph[x].push_back(y);
        cost[x].push_back(c);
        dist[i] = INF;
    }
    dist[1] = 0;
    for(int i = 1; i <= N; i++)
    {
        int v_min = INF;
        int index = -1;
        for(int j = 1; j <= N; j++)
        {
            //cout<<j<<" ";
            if(!vizitat[j] && dist[j] < v_min)
            {
                v_min = dist[j];
                index = j;
            }
        }
        vizitat[index] = 1;
        int lim = graph[index].size();
        for(int t = 0; t < lim; t++)
        {
            int vecin = graph[index][t];
            if(dist[vecin] > dist[index] + cost[index][t])
            {
                dist[vecin] = dist[index] + cost[index][t];
            }
        }
    }

    for(int i = 2; i <= N; i++)
    {
        g<<dist[i]<<" ";
    }
    return 0;
}