#include <fstream>
#include <queue>
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
struct nod{int inf,cost; nod *urm;} *v[50001];
priority_queue<pair<int,int>> q;
int n,m,i,j,k,d[50001],f[50001];
const int inf = 1000000000;
void AdNod(int i, int j, int k)
{
    nod *q = new nod;
    q->inf = j;
    q->cost = k;
    q->urm = v[i];
    v[i] = q;
}
void Dijkstra(int p)
{
    int cst, nd;
    nod *a;
    d[p] = 0;
    q.push(make_pair(-1*d[p], p));
    while(!q.empty())
    {
        cst = q.top().first * -1;
        nd = q.top().second;
        q.pop();
        f[nd] = 1;
        a = v[nd];
        while(a)
        {
            if(f[a->inf] == 0 && d[a->inf] > cst + a->cost)
            {
                d[a->inf] = cst + a->cost;
                q.push(make_pair(-1*d[a->inf], a->inf));
            }
            a = a->urm;
        }
    }

}
int main()
{
    fi >> n >> m;
    for(i=1; i<=n; i++)
    {
        v[i] = NULL;
        d[i] = inf;
    }
    while(fi >> i >> j >> k)
        AdNod(i,j,k);
    Dijkstra(1);
    for(i=2; i<=n; i++)
        fo << d[i] << " ";
    return 0;
}