#include <iostream>
#include <map>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
ifstream be("dijkstra.in");
ofstream ki("dijkstra.out");
const int NMAX = 50000, INF = 2000000000;
int n,m;
int best[NMAX + 1];
bool done[NMAX + 1];
bool bentvan[NMAX + 1];
vector <int> h;

class Ut
{
public:
    int to, ar;
};
vector <Ut> v[NMAX + 1];

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

    }
    for(int i = 1; i <= n; i++)
        best[i] = INF;
    best[1] = 0;
    bentvan[1] = true;
}

bool comparr(int a, int b)
{
    return best[a] > best[b];
}

int main()
{
    beolvas();
    h.push_back(1);
    make_heap(h.begin(), h.end(), comparr);
    while(!h.empty())
    {
        int now = h.front();
        pop_heap(h.begin(), h.end(),comparr);
        h.pop_back();
        if(done[now])
            continue;
        int meret = v[now].size();
        for(int i = 0; i < meret; i++)
        {
            if(!done[v[now][i].to] and best[v[now][i].to] > best[now] + v[now][i].ar)
            {
                best[v[now][i].to] = best[now] + v[now][i].ar;
                h.push_back(v[now][i].to);
                push_heap(h.begin(), h.end(), comparr);
            }
        }
        done[now] = true;
    }

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

    return 0;
}