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

#define MAXINT 9999999

using namespace std;

struct node
{
    int to,val;
};



typedef list<node> LIST_OF_NODES;
typedef vector<LIST_OF_NODES> VECTOR_OF_LISTS_OF_NODES;
typedef list<int> LIST_OF_INTS;
typedef vector<int> VECTOR_OF_INTS;
typedef vector<vector<int> > VECTOR_OF_VECTORS_OF_INTS;


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

void dijkstra(VECTOR_OF_LISTS_OF_NODES &a, VECTOR_OF_INTS &dist, int n, int s)
{
    LIST_OF_INTS active;
    active.push_back(s);

    dist[s] = 0;

    while(!active.empty())
    {
        //if(visited[active.front()]==0)
        int curr = active.front();
        active.pop_front();

        for(LIST_OF_NODES::iterator it = a[curr].begin(); it != a[curr].end(); it++)
        {
            int to = (*it).to;
            int val = (*it).val;
            if(dist[to] > dist[curr]+val)
            {
                dist[to] = dist[curr]+val;
                active.push_back(to);
            }
        }
    }
}

int main()
{

    int n,m;
    fin>>n>>m;
    VECTOR_OF_LISTS_OF_NODES a(n+3);

    node curr;
    int from,to,val;
    for(int i=1;i<=m;i++)
    {

        fin>>from>>to>>val;
        curr.to = to;
        curr.val = val;
        a[from].push_back(curr);

    }


    VECTOR_OF_INTS curr_dist(n+3,MAXINT);
    dijkstra(a,curr_dist,n,1);
    for(int i=2;i<=n;i++)
        if(curr_dist[i] == MAXINT)
            fout<<"0 ";
        else
            fout<<curr_dist[i]<<" ";

    return 0;

}