#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int d[50001], tata[50001], pozHeap[50001];

class comp
{
public:
    int operator()(const int a, const int b)
    {
        return d[a]>d[b];
    }
};
void swap(int *x, int *y)
{
    int aux = *x;
    *x = *y;
    *y = aux;
}

struct minHeap
{
private:
    int *v;
    int sz, cap;
public:
    minHeap(int cap)
    {
        cap=cap;
        sz = 0;
        v =new int[cap];
    }
    ~minHeap()
    {
        delete v;
    }
    int parent(int i)
    {
        return (i-1)/2;
    }
    int left(int i)
    {
        return 2*i+1;
    }
    int right(int i)
    {
        return 2*i+2;
    }

    void Heapify(int i)
    {
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if (l < sz && d[v[l]] < d[v[i]])
            smallest = l;
        if (r < sz && d[v[r]] < d[v[smallest]])
            smallest = r;
        if (smallest != i)
        {
            swap(&v[i], &v[smallest]);
            pozHeap[v[i]]=i;
            pozHeap[v[smallest]]=smallest;
            Heapify(smallest);
        }
    }

    int extrMin()
    {
        int x = v[0];
        if (sz == 1)
        {
            sz--;
            return x;
        }
        v[0]=v[sz-1];
        pozHeap[v[sz-1]]=0;
        sz--;
        Heapify(0);

        return  x;
    }

    void  insertKey(int k)
    {

        sz++;
        int i = sz - 1;
        v[i] = k;
        pozHeap[v[i]]=i;
        while (i != 0 && d[v[parent(i)]] > d[v[i]])
        {

            swap(&v[i], &v[parent(i)]);
            pozHeap[v[i]]=i;
            i = parent(i);
            pozHeap[v[i]]=i;
        }
    }

    void repara(int i)
    {

        while (i != 0 && d[v[parent(i)]] > d[v[i]])
        {
            swap(&v[i], &v[parent(i)]);
            pozHeap[v[i]]=i;
            i = parent(i);
            pozHeap[v[i]]=i;
        }
    }
    int get_sz()
    {
        return sz;
    }



};



int main()
{
    int n, m;
    fin>>n>>m;

    for(int i=1; i<=n; i++)
        d[i]=INT_MAX;
    vector<pair<int,int>> graf[n+1];
    while(m--)
    {
        int x,y,z;
        fin>>x>>y>>z;

        graf[x].push_back(make_pair(y,z));
        //graf[y].push_back(make_pair(x,z));

    }



    d[1]=-1;
    minHeap q(n);
    for(int i=1; i<=n; i++)
        q.insertKey(i);


    d[1]=0;
    while (q.get_sz()>0)
    {


        int u = q.extrMin();
        if(tata[u]==0 && u != 1)
        {
            ;
        }
        else{
        for(auto m : graf[u] )
        {
            if(d[u]+m.second<d[m.first])
            {
                d[m.first]=d[u] + m.second;
                q.repara(pozHeap[m.first]);
                tata[m.first]=u;
            }

        }
        }

    }

    for (int i=2;i<=n;i++)
    {
        if(d[i]==INT_MAX)
            d[i]=0;
        fout<<d[i]<<" ";

    }



    return 0;
}