#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

vector <int> graph[50005];
priority_queue <pair<int,int> > myheap;
int dist[50005];
vector <int> graphc[50005];

void dijkstra(int N, int M)
{
    int t,i,distanta,index,vecin,lim;
    pair <int,int> pereche;
    while(myheap.empty()==0)
    {
        pereche=myheap.top();
        myheap.pop();
        index=pereche.second;
        distanta=-pereche.first;
        if(dist[index]!=distanta)
            continue;
        lim=graph[index].size();
        for(i=0;i<lim;i++)
        {
            vecin=graph[index][i];
            if(dist[vecin] > distanta+graphc[index][i])
            {
                dist[vecin]=distanta+graphc[index][i];
                myheap.push(make_pair(-dist[vecin],vecin));
            }
        }
    }
}
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int N,M,x,y,c,i;
    f>>N>>M;
    for(i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        graph[x].push_back(y);
        graphc[x].push_back(c);
    }
    for(i=2;i<=N;i++)
        {
            dist[i]=1000000005;
            myheap.push(make_pair(-dist[i],i));
        }
    dist[1]=0;
    myheap.push(make_pair(dist[1],1));
    dijkstra(N,M);
    for(i=2;i<=N;i++)
        g<<dist[i]<<" ";
    return 0;
}