#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int Nmax=50000+5;
const int INF=0x3f3f3f3f;
priority_queue<pair<int,int>,vector<pair<int,int>> ,greater<pair<int,int> > >Q;
vector<pair<int,int> >v[Nmax];
bool inq[Nmax];
int DP[Nmax];
int n,m,nod;
int main()
{
    fin>>n>>m;
    for(int i=1,x,y,c;i<=m;++i)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    for(int i=0;i<=n;++i)DP[i]=INF;
    DP[1]=0;Q.push({0,1});
    while(!Q.empty())
    {
        nod=Q.top().second;
        Q.pop();
        inq[nod]=0;
        for(auto i: v[nod])
        {
            if(DP[i.first]>DP[nod]+i.second)
            {
                DP[i.first]=DP[nod]+i.second;
                if(inq[i.first]==0)
                {
                    Q.push({DP[i.first],i.first});
                    inq[i.first]=1;
                }
            }
        }
    }
    for(int i=2;i<=n;++i)
        if(DP[i]!=INF)fout<<DP[i]<<" ";
        else fout<<0<<" ";
    return 0;
}