#include <fstream>
#include <vector>
#include <list>
//#include <pair>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,sursa,dest;
vector < pair<int,int> > vecini[50000]; int dist[50000];
list <int> coada;
list <int>::iterator it;
void adaugare(int x)
{
    it=coada.begin(); it++;
    for(;it!=coada.end();it++)
    {

       if(dist[*it]>dist[x]) {coada.insert(it,x); break;}
    }
    if(it==coada.end()) coada.push_back(x);

}
void schimbare(int x)
{
    it=coada.begin(); it++; int ok=1;
    for(;it!=coada.end();it++)
    {
        if(dist[*it]>dist[x] && ok) {ok=0; coada.insert(it,x);}
        if(*it==x && !ok) {coada.erase(it); break;}
    }
    if(it==coada.end()) coada.push_back(x);
}
void dijkstra()
{
    while(!coada.empty())
    {
        int i,x; x=coada.front();
        //if(x==dest) {break;}
        for(i=0;i<vecini[x].size();i++)
        {
            if(vecini[x][i].second+dist[x]<dist[vecini[x][i].first])
            {
                dist[vecini[x][i].first]=vecini[x][i].second+dist[x];
                schimbare(vecini[x][i].first);
            }
            if(! dist[vecini[x][i].first] && vecini[x][i].first!=sursa)
            {
                dist[vecini[x][i].first]=vecini[x][i].second+dist[x];
                adaugare(vecini[x][i].first);
            }
        }
        coada.pop_front();
    }
}
int main()
{
    f>>n>>m;
    int i,x,y,l,j;
    for(i=0;i<m;i++)
    {
        f>>x>>y>>l;
        vecini[x].push_back(make_pair(y,l));
       // vecini[y].push_back(make_pair(x,l));
    }
    sursa=1;


    coada.push_back(sursa);
    dist[sursa]=0;
    dijkstra();
    for(i=2;i<=n;i++) g<<dist[i]<<' ';
}