#include <fstream>
#include <vector>
#include <set>
using namespace std;

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

const int INF = 0x3f3f3f;

struct muchie
{
    int vf, cost;
};

int n, m, p;

vector<muchie> v[50010];
int d[100010]; //distanta de la nodul initial la i

int main()
{
    fin >> n >> m;
    for(int i = 0 ; i < m ; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        v[a].push_back({b, c});
        //v[b].push_back({a, c});
    }

    for(int i = 0; i <= n + 1; i++)
    {
        d[i] = INF;
    }
    int init = 1;
    d[init] = 0;
    int l = v[init].size();
    set<pair<int, int>> heap;
    heap.insert({0, init});
    while(!heap.empty())
    {
        pair<int, int> tmp = *(heap.begin());
        heap.erase(heap.begin());
        int u = tmp.second;
        l = v[u].size();
        for(int j = 0; j < l; j++)
        {
            int vc = v[u][j].vf;
            int dist = v[u][j].cost;
            if(d[u] + dist < d[vc])
            {
                if(d[vc] != INF)
                {
                    heap.erase(heap.find({d[vc], vc}));
                }
                d[vc] = d[u] + dist;
                heap.insert({d[vc], vc});
            }
        }
    }
    for(int i = 2 ; i <= n; i++)
    {
        if(d[i] != INF)
        {
            fout << d[i] << ' ';
        }
        else fout << 0 << ' ';
    }

    return 0;
}