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

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

int x, y, c, n , m, D[N], viz[N];
vector<pair<int,int>>a[N];
priority_queue<pair<int,int>> q;

void dijkstra()
{
    for(int i = 1; i <= n; i++)
        D[i] = INT_MAX;
    D[1] = 0;
    q.push({0,1});
    while(!q.empty())
    {
            int k = q.top().second;
            q.pop();
            if(!viz[k])
            {
                viz[k] = 1;
                for(auto cr : a[k])
                {
                    if(D[cr.second] > D[k]+cr.first)
                    {
                        D[cr.second] = D[k]+cr.first;
                        q.push({-D[cr.second], cr.second});
                    }
                }
            }
    }
}

int main()
{
    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y >> c;
        a[x].push_back({c,y});
    }
    dijkstra();
    for(int i = 2; i <= n;i ++)
        if(D[i]== INT_MAX)
            fout << 0 << " ";
        else
            fout << D[i] << " ";
    return 0;
}