#include <bits/stdc++.h>

using namespace std;

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

const int dim = 50010;
const int oo = (int) (1e9);

int n, m, dist[dim];
bool incoada[dim];
vector<pair<int, int> > g[dim];

struct cmp
{
    bool operator() (const int &a, const int &b)
    {
        return dist[a] >= dist[b];
    }
};

priority_queue<int, vector<int>, cmp> q;

void read()
{
    in>>n>>m;
    int x, y, c;
    for(int i = 1;i <= n;i++)
        dist[i] = oo;
    for(int i = 1;i <= m;i++)
    {
        in>>x>>y>>c;
        g[x].push_back({y, c});
    }
}

void dijkstra()
{
    dist[1] = 0;
    incoada[1] = 1;
    q.push(1);
    while(!q.empty())
    {
        int curent = q.top();
        incoada[curent] = 0;
        q.pop();

        for(vector<pair<int, int> >::iterator it = g[curent].begin();it != g[curent].end();it++)
        {
            if(dist[it->first] > dist[curent] + it->second)
            {
                dist[it->first] = dist[curent] + it->second;
                    q.push(it->first);
                    incoada[it->first] = 1;
            }
        }
    }
}

void print()
{
    for(int i = 2;i <= n;i++)
        if(dist[i] == oo)
            out<<0<<' ';
        else
            out<<dist[i]<<' ';
}

int main()
{
    read();
    dijkstra();
    print();
    return 0;
}