#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INFINIT 1000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,inq[50001],a,b,cost,cd[50001];
struct imp
{
    int poz,cost;
};
vector <vector <imp>> v(50001);
queue <int> q;
int main()
{
    f>>n>>m;
    for (int i=1; i<=m; i++)
    {
        f>>a>>b>>cost;
        imp ins;
        ins.poz=b;
        ins.cost=cost;
        v[a].push_back(ins);
    }
    for (int i=1; i<=n; i++)
    {
        cd[i]=INFINIT;
    }
    cd[1]=0;
    inq[1]=1;
    q.push(1);
    while (!q.empty())
    {
        int node=q.front();
        inq[node]=0;
        q.pop();
        for (int j=0; j<v[node].size(); j++)
        {
            int t=v[node][j].poz;
            if (cd[t]>cd[node]+v[node][j].cost)
            {
                cd[t]=cd[node]+v[node][j].cost;
                if (inq[t]==0)
                {
                    inq[t]=1;
                    q.push(t);
                }
            }
        }
    }
    for (int i=2; i<=n; i++)
    {
        if (cd[i]==INFINIT)
        {
            cd[i]=0;
        }
        g<<cd[i]<<' ';
    }
    return 0;
}