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

std::ifstream be ("dijkstra.in");
std::ofstream ki ("dijkstra.out");

struct csp
{
    int index, suly;
};

typedef std::vector<std::list<csp> > graf_t;
typedef std::pair<int, int> par;
typedef std::list<csp>::iterator iterator_t;

const int INF = std::numeric_limits<int>::max();

graf_t g;

void dijkstra (graf_t& graf, int start, std::vector<int>& hossz)
{
    hossz.resize (graf.size(), INF);
    std::priority_queue<par, std::vector<par>, std::greater<par>> q;
    hossz[start] = 0;
    q.push (par(0,1));


    while (!q.empty())
    {
        int u = q.top().second;
        int u_suly = g.top().first;
        q.pop();
        if (hossz[u] <= u_suly)
        {
            for (iterator_t i=graf[u].begin(); i != graf[u].end(); i++)
            {
                int v = i->index;
                int suly = i->suly;
                if (hossz[u]+suly < hossz[v])
                {
                    hossz[v] = hossz[u]+suly;
                    q.push(par(hossz[v], v));
                }
            }
        }
    }
}

int main()
{
    int n, m, i, csp1, csp2, suly;

    be >> n >> m;
    g.resize (n+1);
    for (i=0; i<m; i++)
    {
        be >> csp1 >> csp2 >> suly;
        g[csp1].push_back ({csp2, suly});
    }

    std::vector<int> hossz;
    dijkstra (g, 1, hossz);

    for (int i=2; i<hossz.size(); i++)
    {
        if (hossz[i] == INF) ki << "0 ";
        else ki << hossz[i] << " ";
    }
}