#include <bits/stdc++.h>

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

deque < pair <int , int > > graf[50005];
deque <int> ordine;
int distanta[50005];
int vizitat[50005];
void citie()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y,z;
        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_back(1);
    while(!ordine.empty())
    {
        int nod=ordine.back();
        int di=distanta[nod];
        ordine.pop_back();
        for(unsigned int i=0;i<graf[nod].size();i++)
        {

            int nod_nou=graf[nod][i].first;
            int di_nou=graf[nod][i].second;
            int di_actuala=distanta[nod_nou];
            if(di_actuala==infint)
            {
                distanta[nod_nou]=di_nou+di;
            }
            else
            {
                if(di_nou+di<di_actuala)
                    distanta[nod_nou]=di_nou+di;
            }
            if(vizitat[nod_nou]==0)
            {
                vizitat[nod_nou]=1;
                ordine.push_back(nod_nou);
            }


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