#include <iostream>
#include <fstream>
#include <list>
#include <sstream>
#include <string>
#include <queue>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,i,k,j;

struct edge
{
    int node,val;
};

struct comparator
{
    bool operator() (int i, int j)
    {
        if(i<j)
            return false;
        return true;
    }
};

struct t
{
    int parent,dist;
    t():dist(99999){}

}dist[50005];

typedef list<int>::iterator iter;
typedef list<int> LST;
priority_queue<int,vector<int>,comparator> active;

list<edge> a[50005];


iter find_min(LST &active,t *b)
{
    int minn=9999999;
    int mini=0;
    int i=0;
    iter res;
    for(iter it = active.begin();it!=active.end();it++)
    {
        i++;
        int node = (*it);
        if (b[node].dist<minn)
        {
            minn = node;
            mini = i;
        }
    }
    res = active.begin();
    advance(res,mini-1);
    return res;
}
void dijkstra(int s)
{
    //cout<<active.back()<<endl;
    while(!active.empty())
    {

        int curr_node = active.top();
        //cout<<curr_node<<endl;
        //print_list(curr_node);
        list<int> tmp;
        for(list<edge>::iterator it=a[curr_node].begin();it!=a[curr_node].end();it++)
        {

            int val = (*it).val;
            int node = (*it).node;
            //cout<<val<<endl;
            if(dist[node].dist > dist[curr_node].dist + val)
            {
                dist[node].dist = dist[curr_node].dist + val;
                dist[node].parent = curr_node;
                tmp.push_front(node);
            }
        }
        active.pop();
        for(list<int>::iterator it=tmp.begin(); it!=tmp.end();it++)
            active.push((*it));

    }
}

void read_edge()
{
    int m,z,x,c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>z>>x>>c;
        edge curr = {x,c};
        a[z].push_back(curr);
    }
}

int main()
{
    read_edge();
    /// INIT
    dist[1].dist = 0;
    active.push(1);
    dijkstra(1);

    for(int i=2;i<=n;i++)
    {
        if(dist[i].dist == 99999)
            fout<<"0 ";
        else
            fout<<dist[i].dist<<" ";
    }
}