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

using namespace std;

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

const int NMax=50005;
const int oo=(1<<30);

int n,m;
int d[NMax];
bool incoada[NMax];

vector <pair<int,int> > G[NMax];

struct compara
{bool operator()(int x,int y)

{
return d[x]>d[y];
}
};

priority_queue<int,vector<int>,compara> coada;

void cit()
{f>>n>>m;
 for(int i;i<=m;i++)
 {int x,y,c;
  f>>x>>y>>c;
  G[x].push_back(make_pair(y,c));

 }

}

void dijkstra(int nodstart)
{for(int i=1;i<=n;i++)
  d[i]=oo;
  d[nodstart]=0;

  coada.push(nodstart);
  incoada[nodstart]=true;

  while(!coada.empty())
  {
   int nodcurent=coada.top();
   coada.pop();

   incoada[nodcurent]=false;
   for(size_t i=0;i<G[nodcurent].size();i++)
   {int vecin=G[nodcurent][i].first;
    int cost=G[nodcurent][i].second;
    if(d[nodcurent]+cost<d[vecin])
    {d[vecin]=d[nodcurent]+cost;
     if(incoada[vecin]==false)
     {coada.push(vecin);
     incoada[vecin]=true;

     }

    }

   }


  }

}

void afiseaza()
{for (int i=2;i<=n;i++)
{if(d[i]!=oo)
 g<<d[i]<<" ";
 else g<<"0 ";

}
}

int main()
{cit();
 dijkstra(1);
 afiseaza();

    return 0;
}