#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define Nmax 50009
#define oo 2000000000
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
typedef pair<int,int> PP;

int N,M,x,y,z,ante[Nmax],d[Nmax],old_d[Nmax],real_d[Nmax],used[Nmax];
vector < PP > G[Nmax];
priority_queue < PP  , vector < PP > , greater<PP> > pq;

queue < int > Q;
bitset < Nmax > inQ;

inline void ReadInput()
{
    f>>N>>M;
    for(int i=1;i<=M;++i)
        f>>x>>y>>z , G[x].pb(PP(y,z));
}

int Bellman(int Source)
{
    for(int i=1;i<=N;++i)old_d[i]=oo , used[i]=0;
    old_d[Source]=0 , inQ[Source]=1;
    for(Q.push(Source); !Q.empty();Q.pop())
    {
        int node=Q.front();
        inQ[node]=0; ++used[node];
        if(used[node]==N)return 0;
        for(vector<PP>::iterator it=G[node].begin();it!=G[node].end();++it)
            if(d[it->x]>d[node]+it->y)
            {
                old_d[it->x]=old_d[node]+it->y;
                if(!inQ[it->x])Q.push(it->x) , inQ[it->x]=1;
            }
    }
}

void Dijkstra(int S)
{
    for(int i=1;i<=N;++i)d[i]=oo,ante[i]=oo;
    d[S]=0 , ante[S]=S;
    for(pq.push(PP(0,S)); !pq.empty();)
    {
        int  val=pq.top().x,node=pq.top().y;
        pq.pop();
        if(d[node]<val)continue;
        for(vector<PP>::iterator it=G[node].begin();it!=G[node].end();++it)
                if(d[it->x] > d[node]+it->y+old_d[node]-old_d[it->x])
                {
                    d[it->x] = d[node]+it->y+old_d[node]-old_d[it->x];
                    ante[it->x] = node;
                    real_d[it->x] = real_d[node] + it->y;
                    pq.push( PP(d[it->x] , it->x) );
                }
    }
    for(int i=2;i<=N;++i)g<<real_d[i]<<' ';g<<'\n';
}


int main()
{
    ReadInput();
    Dijkstra(1);
    f.close();g.close();
    return 0;
}