#include <bits/stdc++.h>

#define nmax 50000

using namespace std;

vector<pair<int,int> > graf[nmax];
int dij[nmax],k,poz[nmax];
vector<int> h;
int n,m;

bool hcmp(int &a, int &b)
{
    if(dij[a]>dij[b])
    {
        int aux=poz[a];
        poz[a]=poz[b];
        poz[b]=aux;
        return 1;
    }
    return 0;
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    cin>>n>>m;
    for(int i=0;i<n;i++) {dij[i]=nmax*4;poz[i]=-1;}
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        graf[a-1].push_back({b-1,c});
    }
    k=1;
    dij[0]=0;
    h.push_back(0);
    while(h.size()>0)
    {
        int mn=h.front();
        poz[mn]=-1;
        pop_heap(h.begin(),h.end(),hcmp); h.pop_back();
        k--;
        for(int i=0;i<graf[mn].size();i++)
        {
            int next=graf[mn][i].first,cost=graf[mn][i].second;
            if(dij[next]>dij[mn]+cost)
            {
                dij[next]=dij[mn]+cost;
                if(poz[next]==-1)
                {
                    poz[next]=k;
                    h.push_back(next); push_heap(h.begin(),h.end(),hcmp);
                }
                else
                {
                    push_heap(h.begin(),h.begin()+poz[next],hcmp);
                }
            }
        }
    }
    for(int i=1;i<n;i++) {if(dij[i]>=nmax*4) cout<<0<<' '; else cout<<dij[i]<<' ';}
    return 0;
}