#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N,M;
#define infint 2e9

deque < pair <int, int > > graf[50005];
priority_queue <int> ordine;

const int NMAX = 50001;
int distanta[NMAX];
int vizitat[NMAX];
void citie()
{
    int x,y,z;
    fin>>N>>M;
    for(int i=1; i<=M; i++)
    {

        fin>>x>>y>>z;
        graf[x].push_back({y,z});
    }
    for(int i=2; i<=N; i++)
    {
        distanta[i]=infint;
    }
    vizitat[1]=1;
}
void dijkstra()
{
    ordine.push(1);
    while(!ordine.empty())
    {
        int nod=ordine.top();
        vizitat[nod]=1;
        int di=distanta[nod];
        ordine.pop();
        for(unsigned int i=0; i<graf[nod].size(); i++)
        {

            int nod_nou=graf[nod][i].first;
            int di_nou=graf[nod][i].second;
            if(di_nou+di<distanta[nod_nou])
            {
                distanta[nod_nou]=di_nou+di;

                ordine.push(nod_nou);

            }



        }
    }
}
int main()
{
    citie();
    dijkstra();
    for(int i=2; i<=N; i++)
    {
        if(distanta[i]==infint)
            fout<<0<<' ';
        else
            fout<<distanta[i]<<' ';
    }
}