#include <fstream>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <iterator>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int dist[50000];
int n,m;

const int INF=1<<30;

vector <pair <int,int> > graf[50000];
priority_queue <pair <int,int>,vector<pair <int,int> > , greater<pair <int,int>  > > pq;

void read()
{

    f >> n >>m;
    int a,b,c;
    for(int i=0;i<m;i++){
        f >> a >> b >>c;
        graf[a].push_back(make_pair(c,b));
    }

}

void dijkstra()
{
    for(int i=2;i<=n;i++)
        dist[i]=INF;

    dist[1]=0;
    pq.push(make_pair(0,1));
    int w,now,next,cost;

    while(!pq.empty())
    {
        w=pq.top().first;
        now=pq.top().second;
        pq.pop();

        for(vector<pair<int,int> >::iterator it=graf[now].begin();it!=graf[now].end();it++)
        {
            cost=it->first;
            next=it->second;
            if(dist[next]>dist[now]+cost)
            {
                dist[next]=dist[now]+cost;
                pq.push(make_pair(cost,next));
            }
        }
    }


}

int main()
{
    read();
    dijkstra();

      for(int i=2;i<=n;i++)
        g << dist[i] << " ";


    return 0;
}