/* Bellman-Ford */
#include<fstream>
#include<queue>
#include<vector>
using namespace std;

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

int n,m,i,s,dist[50001];
struct muchie{int nod; int cost;};
vector<muchie> v[50001];
int zz;
void bellman_ford(int origin)
{queue <int> q;
 int destination,cost_link;
 q.push(origin);
 while(!q.empty())
 {origin=q.front();
  q.pop(); 
  for(i=0; i<v[origin].size(); i++)
    {destination=v[origin][i].nod;
     cost_link=v[origin][i].cost;
     if(dist[destination]==0 || dist[destination]>dist[origin]+cost_link)
        {dist[destination]=dist[origin]+cost_link;
         zz=dist[destination];
         q.push(destination);}
     }
      
  }
}

int main()
{f>>n>>m;
int a,b,c;
muchie x,y;
for(i=1; i<=m; i++)
{f>>a>>b>>c;
x.nod=b;  x.cost=c;    
//y.nod=a;  y.cost=c;
//v[b].push_back(y);
v[a].push_back(x);
}

s=1;
bellman_ford(s);

for(i=2; i<=n; i++)
  g<<dist[i]<<" ";

f.close();
g.close();
return 0;}