#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <fstream>
using namespace std;

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

struct edge{
    int y, weight;
};

struct compare{
    bool operator()(const edge &a, const edge &b)
    {
        return a.weight > b.weight;
    }
};

vector<int> distances;
vector<pair<int, vector<edge>>> graf;
priority_queue<edge, vector<edge>, compare> q;
int nrEdges, nrNodes;
vector<bool> visited;
void citire()
{
    int weight, from, to;
    edge e;
    fin >> nrNodes >> nrEdges;
    distances = vector<int>(nrNodes+3, 1999999999);
    graf = vector<pair<int, vector<edge>>>(nrNodes+1);
    visited = vector<bool>(nrNodes+1, 0);
    for(int i = 1; i <= nrEdges; i++)
    {
        fin >> from >> to >> weight;
        e.weight = weight;
        e.y = to;
        graf[from].second.push_back(e);
    }
    

}



void dijk()
{
    int currentNode = 1;
    distances[1] = 0;
    edge e;
    e.y = currentNode;
    e.weight = 0;
    q.push(e);
    while (!q.empty())
    {
        currentNode = q.top().y;
        q.pop();
        if(!visited[currentNode])
        {
            for(int i = 0; i < graf[currentNode].second.size(); i++)
            {
                if(distances[graf[currentNode].second[i].y] > distances[currentNode] + graf[currentNode].second[i].weight)
                {
                    distances[graf[currentNode].second[i].y] = distances[currentNode] + graf[currentNode].second[i].weight;
                    e.y = graf[currentNode].second[i].y;
                    e.weight = distances[graf[currentNode].second[i].y];
                    q.push(e);
                }
            }
            visited[currentNode] = 1;
        }
    }

}

int main()
{
    citire();

    dijk();
    for(int i = 2; i <= nrNodes; i++)
    {
        if(distances[i] != 1999999999)
        fout << distances[i] << ' ';
        else
            fout << 0 << ' ';
    }
    return 0;
}




/*
 for(int i = 1; i <= nrNodes; i++)
 {
     cout << i << '\n';
     for(int j = 0; j < graf[i].second.size(); j++)
     {
         cout << graf[i].second[j].y << ' ' << graf[i].second[j].weight << '\n';
     }
 }
 */