#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define inf 0x3f3f3f3f
#define nr 50005

using namespace std;

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

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


priority_queue <ii, vii, greater<ii> > Q;
int n, p;
vi D(nr, inf);
vii G[nr];

void Read()
{
    f >> n >> p;
    int x, y, c;
    while(f >> x >> y >> c)
        G[x].push_back(make_pair(y, c));
}

int main()
{
    Read();
    D[1] = 0;
    Q.push(ii(0, 1));
    while(!Q.empty())
    {
        ii top = Q.top();
        Q.pop();
        int v = top.second, d = top.first;
        if(d <= D[v])
            for(vii :: iterator it = G[v].begin(); it != G[v].end(); ++it)
            {
                int v2 = it->first, cost = it->second;
                if(D[v2] > D[v] + cost)
                {
                    D[v2] = D[v] + cost;
                    Q.push(ii(D[v2], v2));
                }
            }
    }
   for(int i = 2; i <= n; ++i)
        if(D[i] == inf) g << 0 << " ";
        else
        g << D[i] << " ";
}