#include <bits/stdc++.h>

using namespace std;

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

int n, m, visited[50005], x, y, v, start, i, j, inf = 18000000000, p;
struct e
{
    int number_of_neighbourghs;
    vector < int > neighbourghs;
    vector < int > price;
}vertices[50005];
queue < int > Q;


void outData()
{
    for(int q = 1; q <= n; q++)
        cout << visited[q] << " ";
    cout << endl;
}
void run_algorithm()
{
    p = 1;
    start = p;
    visited[start] = 0;
    Q.push(start);
    while(!Q.empty())
    {
        x = Q.front();
        Q.pop();
        for(i = 0; i < vertices[x].neighbourghs.size(); i++)
        {
            if(visited[x] + vertices[x].price[i] < visited[vertices[x].neighbourghs[i]])
            {
                visited[vertices[x].neighbourghs[i]] = visited[x] + vertices[x].price[i];
                Q.push(vertices[x].neighbourghs[i]);
            }
        }
         ///outData();
    }

}

int main()
{
    in >> n >> m;
    for(i = 1; i <= m; i++)
    {
        in >> x >> y >> v;
        vertices[x].number_of_neighbourghs++;
       // vertices[y].number_of_neighbourghs++;
        vertices[x].neighbourghs.push_back(y);
       // vertices[y].neighbourghs.push_back(x);
        vertices[x].price.push_back(v);
      //  vertices[y].price.push_back(v);
    }
    for(i = 1; i <= n; i++)
        visited[i] = inf;
    run_algorithm();
    for(int i = 2; i <= n; i++)
        if(visited[i] == inf)
        out << "0 ";
        else
        out << visited[i] << " ";
    return 0;
}