#include <iostream>
#include <fstream>
#include <vector>
#define INF 4294967295
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
int n,m;
vector <pair<int,int> >V[50005];
vector <pair<int,long> >H;
long D[50005];
void rebuild()
{
    if(H.size()==1)
        H.pop_back();
    else
    {
        int last=H.size()-1;
        swap(H[0],H[last]);
        H.pop_back();
        last--;
        int G=0;
        int parent=0;
        while(G==0 && parent<=last)
        {
            int poz=parent;
            int child1=parent*2+1;
            int child2=parent*2+2;
            if(child1<=last)
                if(H[child1].second>H[poz].second)
                    poz=child1;
            if(child2<=last)
                if(H[child2].second>H[poz].second)
                    poz=child2;
            if(poz==parent)
            {
                G=1;
                continue;
            }else
            {
                swap(H[parent],H[poz]);
                parent=poz;
            }
        }
    }
}
void heapify()
{
    int child=H.size()-1;
    int g=0;
    while(g==0 && child>0)
    {
        int parent=(child-1)/2;
        if(H[parent].second>H[child].second)
        {
            g=1;
            continue;
        }else
        {
            swap(H[parent],H[child]);
            child=parent;
        }
    }
}
void Dijkstra()
{
    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,D[vecin]));
                heapify();
            }else
                D[vecin]=min(D[vecin],D[vertex]+V[vertex][i].second);
        }
    }
}
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));
    }
    D[1]=0;
    for(int i=2;i<=n;i++)
        D[i]=INF;
    H.push_back(make_pair(1,0));
    Dijkstra();
    for(int i=2;i<=n;i++)
    {
        if(D[i]==INF)
            fo<<0<<" ";
        else
            fo<<D[i]<<" ";
    }
    return 0;
}