#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

int cost[50001];
int pct, edges;
queue<int> coada;
vector< pair <int, int> > muchii[50002];
int main()
{
    f>>pct>>edges;
    for(int i=1;i<=edges;++i)
    {
        int c,b,a;
        f>>a>>b>>c;
        muchii[a].push_back(make_pair(b,c));

    }
     for(int i=1;i<=pct;++i)
       cost[i]=1e9;
    int nod=1;
    cost[1]=0;
    coada.push(1);
    while(!coada.empty())
    {

        nod=coada.front();
        coada.pop();
        for(int i=0; i<muchii[nod].size(); ++i)
        {
            pair<int, int> copil=muchii[nod].at(i);
         //   add(copil.second);

            if(cost[copil.first]>cost[nod]+ copil.second)
            {
               cost[copil.first]=cost[nod]+ copil.second;
            }
            coada.push(copil.first);

        }
       // int minn=getMin();
      //  cout<<minn<<" ";
      //  popMin();
    }
    for(int i=2;i<=pct;++i)
        g<<cost[i]<<" ";
    return 0;
}