#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <sstream>
using namespace std;
const int INF = 2100000000;
const int NMAX = 50005;
const char inputFile[] = "dijkstra.in";
const char outputFile[] = "dijkstra.out";

int dist[NMAX],tata[NMAX];
vector< pair<int,int> >graf[NMAX];
vector<int> punctControl;
int n, m;
class Cmp
{
public:
    bool operator()(int a, int b)
    {
        return dist[a] > dist[b];
    }
};

void citeste()
{
    ifstream f(inputFile);
    f>>n>>m;
    int a, b, c;
    for(int i = 0; i < m; i++)
        {
            f >> a >> b >> c;
            graf[a].push_back(make_pair(b,c));
        }
    /*int x;
    while(f >> x)
        punctControl.push_back(x);*/
}

void dijkstra(int sursa)
{
    //priority_queue<int, vector<int>, Cmp> q;
    queue<int> q;
    dist[sursa] = 0;
    tata[sursa] = -1;
    q.push(sursa);
    for(int i = 1; i <= n; i++)
    {
        if(i != sursa)
        {
            dist[i] = INF;
            tata[i] = -1;
        }
    }
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        for(unsigned int i = 0; i < graf[nod].size(); i++)
        {
            int cost = dist[nod] + graf[nod][i].second;
            if(cost < dist[graf[nod][i].first])
            {
                q.push(graf[nod][i].first);
                tata[graf[nod][i].first] = nod;
                dist[graf[nod][i].first] = cost;
            }
        }
        //how do I update a priority queue?
    }
}

int main()
{
    citeste();
    dijkstra(1);
    ofstream g(outputFile);
    for(int i = 2; i <=n; i++)
        if(dist[i] == INF)
            g<<'0'<<' ';
        else
            g<<dist[i]<<' ';
    return 0;
}