#include <iostream>
#include <fstream>
#include <set>
#include <cstring>
#include <vector>
#define dim 50001

using namespace std;

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

vector < pair <int,int> > v[dim];
vector < pair <int,int> > ::iterator it;
set < pair <int,int> > h;
const int INF = 0x3f3f3f3f;

int main()
{
    int n,m,i,j,price,node,new_node,d[dim];
    f >> n >> m;
    while(m)
    {
        m--;
        f >> i >> j >> price;
        v[i].push_back(make_pair(j,price));
    }
    h.insert( make_pair(0,1));
    memset(d, INF, sizeof d);
    d[1] = 0;
    while( not h.empty())
    {
        price = h.begin() -> first;
        node = h.begin() -> second;
        h.erase(h.begin());
        for(it = v[node].begin(); it != v[node].end(); it++)
        {
            new_node = it -> first;
            price = it -> second;
            if(d[new_node] > d[node] + price)
            {
                if(d[new_node] != INF)
                    h.erase(h.find(make_pair(d[new_node], new_node)));
                d[new_node] = d[node] + price;
                h.insert(make_pair(d[new_node], new_node));
            }
        }
    }
    for(i=2; i<=n; ++i)
        if(d[i] == INF)
            g << 0 << " ";
        else
            g << d[i] << " ";
    return 0;
}