#include <bits/stdc++.h>

using namespace std;

const int dim = 50100;
const int dim1 = 250100;
const int oo = (int) (1e9);

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

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

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

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

void dijsktra()
{
    priority_queue<int, vector<int>, cmp> q;
    int curent;
    dist[1] = 0;
    incoada[1] = true;
    q.push(1);
    while(!q.empty())
    {
        curent = q.top();
        incoada[curent] = false;
        q.pop();
        for(vector<pair<int, int> >::iterator it = muchii[curent].begin(); it != muchii[curent].end(); it++)
        {
            if(dist[it->first] > dist[curent] + it->second)
            {
                dist[it->first] = dist[curent] + it->second;
                if(!incoada[it->first])
                {
                    q.push(it->first);
                    incoada[it->first] = true;
                }
            }
        }
    }
}

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

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