#include <fstream>
#define DIM 50001
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

struct muchie
{
    int vf, l;
};

vector <muchie> nod[DIM];

muchie temp;

int dist[DIM], h[DIM], p, inside[DIM], lung, n, m, a, b, lungime, vfc;

int top_heap()
{
    return h[1];
}

void add(int x)
{
    int p;
    lung++;
    h[lung]=x;
    p=lung;
    while(dist[h[p/2]]>dist[h[p]]&&p>1)
    {
        swap(h[p/2], h[p]);
        p/=2;
    }
}

void pop_heap()
{
    int p;
    swap(h[1], h[lung]);
    lung--;
    p=1;
    while((dist[h[2*p]]>dist[h[1]]&&2*p<=lung)||(dist[h[2*p+1]]>dist[h[p]]&&2*p+1<=lung))
    {
        if((dist[h[2*p]]<dist[h[2*p+1]]&&(2*p+1)<=lung)||(2*p==lung))
        {
            swap(h[p], h[2*p]);
            p*=2;
        }
        else
        {
            swap(h[p], h[2*p+1]);
            p=2*p+1;
        }
    }
}


int main()
{
    ifstream in ("dijkstra.in");
    ofstream out ("dijkstra.out");
    in>>n>>m;
    while(m--)
        {
            in>>a>>b>>lungime;
            temp.vf=b;
            temp.l=lungime;
            nod[a].push_back(temp);
        }
    add(1);
    while(lung>0)
    {
        do
        {
            vfc=top_heap();
            pop_heap();
        }while(inside[vfc]);
        inside[vfc]=1;
        for(int j=0; j<nod[vfc].size(); ++j)
        {
            temp=nod[vfc][j];
            if(dist[temp.vf]==0||dist[temp.vf]>dist[vfc]+temp.l)
            {
                dist[temp.vf]=dist[vfc]+temp.l;
                add(temp.vf);
            }
        }
    }
    for(int i=2; i<=n; ++i)
        out<<dist[i]<<" ";
    out<<"\n";
    in.close();
    out.close();
    return 0;
}