#include <bits/stdc++.h>
#define Nmax 50005
#define INF 1 << 30

using namespace std;

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

int n, m;
int dist[Nmax];
bool in_stack[Nmax];

vector < pair <int,int> > v[Nmax];

struct comp
{
    bool operator()(int x, int y)
    {
        return dist[x] > dist[y];
    }
};

priority_queue<int, vector<int>, comp> Q;

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

void dijkstra(int nodStart)
{
    for(int i = 1; i <= n; i++)
        dist[i] = INF;

    dist[nodStart]=0;

    Q.push(nodStart);
    in_stack[nodStart] = 1;

    while(!Q.empty())
    {
        int nc = Q.top();
        Q.pop();

        in_stack[nc] = 0;
        for(size_t i = 0; i < v[nc].size(); i++)
        {
            int vecin = v[nc][i].first;
            int Cost = v[nc][i].second;
            if(dist[nc] + Cost < dist[vecin])
            {
                dist[vecin] = dist[nc] + Cost;
                if(in_stack[vecin] == 0)
                {
                    Q.push(vecin);
                    in_stack[vecin] = 1;
                }
            }
        }
    }
}

void output()
{
    for(int i = 2; i <= n; i++)
    {
        if(dist[i] != INF)
            g << dist[i] << " ";
        else
            g << "0 ";
    }
}

int main()
{
    input();
    dijkstra(1);
    output();
}