#include <iostream>
#include <queue>
#include <vector>
#define INF 999999
#include <fstream>

using namespace std;

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

struct node
{
    int dist = INF;
    int father;
    bool used = false;
    vector <int> n;
    vector <int> d;
};

node G[100000];
priority_queue <int, vector<int>, greater<int> > Q;
int N, M;


void Input()
{
    f>>N>>M;
    int x, y, d;
    for (int i = 0; i < M; ++i)
    {
        f>>x>>y>>d;
        G[x].n.push_back(y);
        G[x].d.push_back(d);
    }
}

void dij(int start)
{
    Q.push(start);
    int current = start;
    G[current].dist = 0;
    while(!Q.empty())
    {
        G[current].used = true;
        for (int i = 0; i < G[current].n.size(); ++i)
        {
            int newn = G[current].n[i];
            if (!G[newn].used && G[newn].dist > G[current].dist + G[current].d[i])
            {
                G[newn].dist = G[current].dist + G[current].d[i];
                Q.push(newn);
            }
        }
        current = Q.top();
        Q.pop();
    }
}

int main()
{
    Input();
    dij(1);
    for (int i = 2; i <= N; ++i)
        if (G[i].used)
            g<<G[i].dist<<" ";
        else
            g<<0<<" ";
    return 0;
}