#include<fstream>
#include<queue>
#include<vector>
#include<bitset>
#define NMAX 666013
using namespace std;

struct muchie{
   unsigned nod;
   int cost;
};
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
vector<muchie> G[NMAX];
bitset<NMAX> viz;
queue<unsigned> Q;
unsigned i, N, M, x, D[NMAX];

void read()
{
     f>>N>>M;
     muchie aux;
     for(i=0;i<M;i++) f>>x>>aux.nod>>aux.cost, G[x].push_back(aux);
}

void solve()
{
     D[1]=0;
     viz[1]=1;
     Q.push(1);
     for(i=2;i<=N;i++) D[i]=NMAX;
     while(Q.size())
     {
        unsigned nod=Q.front();
        Q.pop();
        for(i=0;i<G[nod].size();i++)   
            if(D[nod]+G[nod][i].cost<D[G[nod][i].nod]){
                D[G[nod][i].nod]=D[nod]+G[nod][i].cost;   
                if(!viz[G[nod][i].nod]) Q.push(G[nod][i].nod), viz[G[nod][i].nod] = 1;
            } 
     }
}

void write() {for(i=2;i<=N;i++) g<<(D[i]<NMAX ? D[i] : 0)<<" ";}

int main()
{
   read();
   solve();
   write();   
}