#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define oo 0x3f3f3f3f
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector < pair <int,int> > v[50005];
int N,M,d[50005],viz[50005],nod;
struct heap
{
    int nod, cost;
    heap(int n, int c) : nod(n),cost(c) {}
    bool operator < (const heap &other) const
    {
        return cost > other.cost;
    }
};
priority_queue <heap> q;
int main()
{
    fin>>N>>M;
    for(int i=0; i<M; i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    memset(d,oo,sizeof d);
    q.emplace(1,0);
    d[1]=0;
    while (!q.empty())
    {
        int nod = q.top().nod, cost = q.top().cost;
        q.pop();
        if (cost == d[nod])
        {
            for (auto i : v[nod])
            {
                int dist = d[nod] + i.second;
                if (dist < d[i.first])
                {
                    d[i.first] = dist;
                    q.emplace(i.first, d[i.first]);
                }
            }
        }
    }
    for (int i = 2; i <= N; i++)
    {
        if (d[i] == oo)
            fout << 0;
        else
            fout << d[i];
        fout << ' ';
    }
    fout << '\n';
    return 0;
}