#include <fstream>
#include <vector>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
#define Nmax 50001
#define INF 2000000000

int n, nr = 0;
vector< pair<int, int> > G[Nmax];
int c[Nmax], NR[Nmax];
int heap[Nmax], poz[Nmax];

void read() ;
void push(int) ;
int get_min() ;

int main()
{
    int vf;
    vector< pair<int, int> >::iterator it;
    read();

    for(vf = 2; vf <= n; ++vf) c[vf] = INF;

    push(1);
    while(nr > 0)
    {
        vf = get_min();
        for(it = G[vf].begin(); it != G[vf].end(); ++it)
            if(c[it -> first] > (it -> second) + c[vf])
            {
                c[it -> first] = (it -> second) + c[vf];
                ++NR[it -> first];
                if(NR[it -> first] > n)
                {
                    fout << "Ciclu negativ!\n";
                    return 0;
                }
                push(it -> first);
            }
    }

    for(vf = 2; vf <= n; ++vf)
        fout << c[vf] << ' ';
    return 0;
}

void read()
{
    int a, b, cost, m;
    fin >> n >> m;
    for(; m; --m)
    {
        fin >> a >> b >> cost;
        G[a].push_back(make_pair(b, cost));
        //G[b].push_back(make_pair(a, cost));
    }
}

void push(int vf)
{
    if(poz[vf] == 0) heap[++nr] = vf, poz[vf] = nr;

    int p = poz[vf];
    while(p > 1 && c[heap[p]] < c[heap[p / 2]])
    {
        swap(heap[p], heap[p / 2]);
        poz[heap[p]] = p;
        poz[heap[p / 2]] = p / 2;
        p >>= 1;
    }
}

int get_min()
{
    int rez = heap[1]; poz[rez] = 0;
    heap[1] = heap[nr--]; poz[heap[1]] = 1; heap[nr + 1] = 0;

    int p;
    for(p = 1; 2 * p <= nr;)
    {
        if(2 * p == nr)
        {
            if(c[heap[p]] > c[heap[2 * p]])
            {
                swap(heap[p], heap[2 * p]);
                poz[heap[p]] = p;
                poz[heap[2 * p]] = 2 * p;
            }
            return rez;
        }
        if(c[heap[2 * p]] < c[heap[2 * p + 1]])
        {
            if(c[heap[p]] > c[heap[2 * p]])
            {
                swap(heap[p], heap[2 * p]);
                poz[heap[p]] = p;
                poz[heap[2 * p]] = 2 * p;
                p = 2 * p;
            }
            else return rez;
        }
        else
        {
            if(c[heap[p]] > c[heap[2 * p + 1]])
            {
                swap(heap[p], heap[2 * p + 1]);
                poz[heap[p]] = p;
                poz[heap[2 * p + 1]] = 2 * p + 1;
                p = 2 * p + 1;
            }
            else return rez;
        }
    }
    return rez;
}