#include <bits/stdc++.h>
#define inf 10000000
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int n, m, i, x, y, c, f[50001], d[50001], minim, nod;
vector <pair<int, int > > L[50001];
int main ()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        L[x].push_back({y,c});
    }
    d[1]=0;
    for (i=2; i<=n; i++)
        d[i]=inf;
    ///la fiecare pas ma uit dupa elementele inca nevizitate care au distanta minima;
    for (int j=1; j<=n;j++)
    {
        minim=inf;
        for (i=1; i<=n; i++)
            if (!f[i] && d[i]<minim)
            {
                minim=d[i];
                nod=i;
            }
            f[nod]=1;
            ///relaxez toate drumurile catre vecinii lui nod prin nod
            for (i=0; i<L[nod].size(); i++)
            {
                int vecin=L[nod][i].first;
                int cost=L[nod][i].second;
                if (d[vecin]>d[nod]+cost && !f[vecin])
                    d[vecin]=d[nod]+cost;
            }
    }
    for (i=2; i<=n; i++)
        fout<<d[i]<<" ";
}