#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#define Nmax 50005
#define oo (1<<30)
using namespace std;
int D[Nmax],n,m;
bool viz[Nmax];
vector < pair <int , int> > G[Nmax];
struct comparaDist
{
    bool operator()(int x,int y)
    {
        return D[x] > D[y];
    }
};
priority_queue < int , vector < int > , comparaDist > coada;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
void Dijkstra(int nodS)
{
    for(int i=1;i<=n;i++)
    D[i]=oo;
    D[nodS]=0;
    coada.push(nodS);
    viz[nodS]=1;
    while(!coada.empty())
    {
        int nod=coada.top();
        coada.pop();
        viz[nod]=0;
        for(unsigned int i=0;i<G[nod].size();i++)
        {
            int vecin=G[nod][i].first;
            int cost=G[nod][i].second;
            if(D[nod]+cost < D[vecin])
                {  D[vecin]=D[nod]+cost;

               if(viz[vecin]==0)
               {
                   viz[vecin]=1;
                   coada.push(vecin);
               }
           }
        }
    }
}
int main()
{    in>>n>>m;
for(int i=1;i<=m;i++)
{  int x,y,c;
   in>>x>>y>>c;
   G[x].push_back(make_pair(y,c));
}
Dijkstra(1);
for(int i=2;i<=n;i++)
if(D[i]!=oo) out<<D[i]<<' ';
else out<<0<<' ';

    return 0;
}