#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50001
#define INF 123123123
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
struct varf{
   int x,c;
};
vector<varf>G[NMAX];
int n,start=1,m;
int cmin[NMAX];
int pre[NMAX];
bool M[NMAX];
priority_queue< pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> >H;
void citire();
void initializare();
void dijkstra();
void afisare();
int main()
{
    citire();
    initializare();
    dijkstra();
    afisare();
    return 0;
}
void citire()
{
    int x,y,cost;
    varf vf;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y>>cost;
        vf.x=y;
        vf.c=cost;
        G[x].push_back(vf);
    }
}
void initializare()
{
    int i;
    pair<int,int> p;
    for(i=1;i<=n;i++)
    {
        cmin[i]=INF;
        pre[i]=start;
    }
    pre[start]=0;
    cmin[start]=0;
    M[start]=1;
    for(i=0;i<G[start].size();i++)
    {
        cmin[G[start][i].x]=G[start][i].c;
        p.first=G[start][i].c;
        p.second=G[start][i].x;
        H.push(p);
    }
}
void dijkstra()
{
    int i,k,vfmin,cost;
    pair<int,int> p;
    for(k=1;k<n && !H.empty();)
    {
        p=H.top();
        H.pop();
        vfmin=p.second;
        cost=p.first;
        if(M[vfmin]==0)
        {
            M[vfmin]=1;
            //optimizez costurile de la vfmin la varfurile adiacente cu el
            for(i=0;i<G[vfmin].size();i++)
            {
                if(cmin[G[vfmin][i].x]>cost+G[vfmin][i].c)
                {
                    cmin[G[vfmin][i].x]=cost+G[vfmin][i].c;
                    pre[G[vfmin][i].x]=vfmin;
                    p.first=cmin[G[vfmin][i].x];
                    p.second=G[vfmin][i].x;
                    H.push(p);
                }
            }
            k++;
        }
    }
}
void afisare()
{
    for(int i=2;i<=n;i++)
    {
        if(cmin[i]!=INF) cout<<cmin[i]<<" ";
        else cout<<0<<" ";
    }
}