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

using namespace std;

const int NMAX = 50005;
const int MAX = 1e9 + 7;

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

int N, M;
int shortest[NMAX + 5];
bool visited[NMAX + 5];
vector <pair<int, int>> g[NMAX + 5];
priority_queue<pair<int, int>> pq;

void update(int x)
{
    for(auto y: g[x])
    {
        int nod = y.second, pret = y.first;
        if(shortest[x] + pret < shortest[nod])
        {
            shortest[nod] = shortest[x] + pret;
            pq.push({-shortest[nod], nod});
        }
    }
}

int main()
{
    fin >> N >> M;
    for(int i = 0; i <= N; i++)
        shortest[i] = MAX;
    for(int i = 1; i <= M; i++)
    {
        int x, y, pret;
        fin >> x >> y >> pret;
        g[x].push_back({pret, y});
    }
    shortest[1] = 0;
    pq.push({0, 1});
    while(!pq.empty())
    {
        int current = pq.top().second;
        pq.pop();
        if(!visited[current])
        {
            visited[current] = 1;
            update(current);
        }
    }

    for(int i = 2; i <= N; i++)
    {
        if(shortest[i] == MAX)
            fout << "0 ";
        else
            fout << shortest[i] << " ";
    }

    fin.close();
    fout.close();
    return 0;
}