#include <iostream>
#include <fstream>
#include <vector>
#define INF 2147483640
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
int n,m;
vector <pair<int,int> >V[50001];
vector <pair<int,int> >H;
int D[50001];
void heapify()
{
    int child=H.size()-1;
    int G=1;
    while(G==1 && child>0)
    {
        int parent=(child-1)/2;
        if(H[parent].second>H[child].second)
        {
            swap(H[parent],H[child]);
            child=parent;
        }else
        {
            G=0;
            continue;
        }
    }
}
void rebuild()
{
    if(H.size()==1)
        H.pop_back();
    else
    {
        int ultimul=H.size()-1;
        swap(H[ultimul],H[0]);
        H.pop_back();
        int g=0;
        int parent=0;
        while(g==0 && parent<=H.size()-1)
        {
            int poz=parent;
            int child1=parent*2+1;
            int child2=parent*2+2;
            if(child1<=H.size()-1)
                if(H[child1].second<H[poz].second)
                    poz=child1;
            if(child2<=H.size()-1)
                if(H[child2].second<H[poz].second)
                    poz=child2;
            if(poz==parent)
            {
                g=1;
                continue;
            }else
            {
                swap(H[poz],H[parent]);
                parent=poz;
            }
        }
    }
}
void Dijkastra(int firstNode)
{
    while(!H.empty())
    {
        int vertex=H[0].first;
        rebuild();
        for(int i=0;i<V[vertex].size();i++)
        {
            int vecin=V[vertex][i].first;
            if(D[vecin]==INF)
            {
                D[vecin]=D[vertex]+V[vertex][i].second;
                H.push_back(make_pair(vecin,V[vertex][i].second+D[vertex]));
                heapify();
            }else
                D[vecin]=min(D[vecin],V[vertex][i].second+D[vertex]);
        }
    }
}
int main()
{
    fi>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,C;
        fi>>x>>y>>C;
        V[x].push_back(make_pair(y,C));
    }
    for(int i=2;i<=n;i++)
        D[i]=INF;
    H.push_back(make_pair(1,0));
    Dijkastra(1);
    for(int i=2;i<=n;i++)
        fo<<D[i]<<" ";
    return 0;
}