#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");

struct muchie
{
    int nod, cost;
}temp;


vector<muchie> mu[50004];
bool vis[50004];
int dist[50004];


struct mycmp
{
    bool operator ()(int a, int b)
    {
        return dist[a] > dist[b];
    }
};

priority_queue<int, vector<int>, mycmp> pq;

void dijkstra(int start, int n)
{
    pq.push(start);
    for (int i = 2; i <= n; i++)
        dist[i] = 2e9;
    while(!pq.empty())
    {
        int aux = pq.top();
        vis[aux] = 1;
        //out<<aux<<" : ";

        for(int i = 0 ; i < mu[aux].size() ; i++)
        {
            if(!vis[mu[aux][i].nod])
            {
                //vis[mu[aux][i].nod] = 1;
                //out<<mu[aux][i].nod<<" , ";
                pq.push(mu[aux][i].nod);
                if( dist[aux] + mu[aux][i].cost < dist[mu[aux][i].nod])
                {
                    dist[mu[aux][i].nod] = dist[aux] + mu[aux][i].cost;
                }
            }
        }
        //out<<'\n';

        pq.pop();
    }
}

void citire(int m)
{
    int j;
    for(j = 1 ; j <= m; j++)
    {
        int y;
        in >> y >> temp.nod >> temp.cost;
        mu[y].push_back(temp);
    }
}

int main()
{
    int i, n, m;

    in >> n >> m;

    citire(m);

    dijkstra(1, n);

    for(i = 2 ; i <= n ; i++)
    {
        if(vis[i] == 0)
            out << 0 <<" ";
        else
            out<<dist[i]<<" ";
    }
    return 0;
}