#include <fstream>//100p varianta ultima
#define inf 2000000000
#define Nmax 250003
using namespace std;
ifstream f("dijkstra.in"); ofstream g("dijkstra.out");
struct muchie{ int x,y,c;};
int i,n,m,x,y,cost,d[Nmax];
muchie mu[Nmax];
void bellman_ford (int s) //ciudat
 {
  int i,j,ok;
  for (i=1; i<=n; i++) d[i]=inf;
  for (j=1; j<=m; j++)
    if(mu[j].x==s)d[mu[j].y]=mu[j].c;

  do{
      ok=1;
      for (j=1;j<=m; j++ )
         if(d[mu[j].y]>d[mu[j].x]+mu[j].c)
            d[mu[j].y]=d[mu[j].x]+mu[j].c , ok=0;
}while(!ok);
}
int main () {

  f>>n>>m;
  for (i = 1; i <= m; i++)
    {
      f >> x >> y>>cost;
      mu[i].x=x; mu[i].y=y; mu[i].c=cost;
    }

  bellman_ford(1);
  for (i=2; i<=n; i++)
       if(d[i]!=inf) g<<d[i]<<" ";
         else g<<0<<" ";
  return 0;
}
////Bellman Ford O(m*n) 100p
//#include<fstream>
//#include <deque>
//#include<vector>
//#define inf 1000000000
//#define NMax 50003
//using namespace std;
//ifstream f("dijkstra.in");
//ofstream g("dijkstra.out");
//struct two{int urm,cost;};
//vector <pair<int,int> >A[NMax];
//deque <int> coada;
//int i,m,n,a,b,c,nod,d[NMax];
//int main()
//{
//    f>>n>>m;
//    for(i=1;i<=m;++i)
//     {
//        f>>a>>b>>c;
//        A[a].push_back(make_pair(b,c));
//     }
//    for(i=1;i<=n;++i) d[i]=inf;
//    coada.push_back(1);d[1]=0;
//    while (!coada.empty())
//     {
//        nod=coada.front();coada.pop_front();
//
//        for(i=0;i<A[nod].size();++i)
//            if(d[nod]+A[nod][i].second < d[A[nod][i].first])
//            {
//                coada.push_back(A[nod][i].first);
//                d[A[nod][i].first]=d[nod]+A[nod][i].second;
//            }
//     }
//    for ( int i = 2; i <= n; i++ )
//        if(d[i] == inf) g<<0<<" ";else g<< d[i]<<" ";
//    f.close();
//    g.close();
//}


////Dijkstra O(nlog(n)) 100p  cu STL tipul SET (arbori de cautare  echilibrati )
//// SET - Toate operatiile se fac in O(log(n))
//#include <fstream>
//#include <set>
//#include <vector>
//#define NMax 50100
//#define inf 1000000000
//using namespace std;
//ifstream f("dijkstra.in");
//ofstream g("dijkstra.out");
//int n, m, d[NMax]; vector<int> G[NMax], C[NMax];
//set< pair<int, int> > T;
//int i, x, y, costul;
//void solve(void)
//{
//    int i, val, x;
//    for(i = 2; i <= n; i++) d[i] = inf;
//    T.insert( make_pair(0, 1) );
//    while( T.size() > 0 )
//    {
//        val = (*T.begin()).first;
//        x = (*T.begin()).second;
//        T.erase(*T.begin());
//        for(i = 0; i < G[x].size(); i++)
//         if(d[ G[x][i] ] > val + C[x][i] )
//         {
//            d[ G[x][i] ] = val + C[x][i];
//            T.insert(make_pair(d[G[x][i]],G[x][i]));
//         }
//    }
//}
//int main(void)
//{
//
//    f>>n>>m;
//    for(i = 1; i <=m ; i++)
//    {
//        f>>x>>y>>costul;
//        G[x].push_back(y); C[x].push_back(costul);
//    }
//    solve();
//    for ( int i = 2; i <= n; i++ )
//        if(d[i] == inf) g<<0<<" ";else g<< d[i]<<" ";
//    g<<'\n';
//    return 0;
//}
////Dijkstra O(nlog(n)) 80p  cu STL tipul SET (arbori de cautare  echilibrati )
//// SET - Toate operatiile se fac in O(log(n))
//
//#include <fstream>
//#include <set>
//#include <vector>
//#define NMax 50100
//#define inf 1000000000
//using namespace std;
//ifstream f("dijkstra.in");
//ofstream g("dijkstra.out");
//int n, m, d[NMax]; vector<int> G[NMax], C[NMax];
//set< pair<int, int> > T;
//int i, x, y, costul;
//void solve(void)
//{
//    int i, val, x;
//    for(i = 2; i <= n; i++) d[i] = inf;
//    T.insert( make_pair(1, 0) );//?
//    while( T.size() > 0 )
//    {
//        x = (*T.begin()).first;
//        val = (*T.begin()).second;
//        T.erase(*T.begin());
//        for(i = 0; i < G[x].size(); i++)
//         if(d[ G[x][i] ] > val + C[x][i] )
//         {
//            d[ G[x][i] ] = val + C[x][i];
//            T.insert(make_pair(G[x][i],d[G[x][i]]));
//         }
//    }
//}
//int main(void)
//{
//
//    f>>n>>m;
//    for(i = 1; i <=m ; i++)
//    {
//        f>>x>>y>>costul;
//        G[x].push_back(y); C[x].push_back(costul);
//    }
//    solve();
//    for ( int i = 2; i <= n; i++ )
//        if(d[i] == inf) g<<0<<" ";else g<< d[i]<<" ";
//    g<<'\n';
//    return 0;
//}
//Dijkstra O(nlog(n)) 100p  cu STL tipul SET (arbori de cautare  echilibrati )
// SET - Toate operatiile se fac in O(log(n))

////Dijkstra 40p  cu memorare graf cu liste de adiacenta O(n*n)clasic nu se incadreaza in timp
//#include <fstream>
//#define NMax 50003
//#define inf 1000000000
//using namespace std;
//ifstream f("dijkstra.in");
//ofstream g("dijkstra.out");
//struct Nod
//{
//    int nod, cost;
//    Nod *next;
//};
//int n, m,x,y,costul;
//Nod *Vecin[NMax];
//int d[NMax], S[NMax];
//void adauga(int x, int y, int costul)
//{
//    Nod *q = new Nod;
//    q->nod = y;
//    q->cost = costul;
//    q->next = Vecin[x];
//    Vecin[x] = q;
//}
//
//void dijkstra()
//{
//    for ( int i = 2; i <= n; i++ ) d[i] = inf;
//    int mini, pmin = 0;
//    for ( int i = 1; i <= n; i++ )
//    {
//        mini = inf;
//        for ( int j = 1; j <= n; j++ )
//            if ( d[j] < mini && !S[j] )  {mini = d[j]; pmin = j;}
//
//        S[pmin] = 1;
//        Nod *t = Vecin[pmin];
//        while ( t )
//        {
//            if ( d[ t->nod ] > d[pmin] + t->cost )
//                       d[ t->nod ] = d[pmin] + t->cost;
//            t = t->next;
//        }
//    }
//}
//
//int main()
//{
//    f>>n>>m;
//    for ( int i = 1; i <= m; i++ )
//    {
//        f>>x>>y>>costul;
//        adauga(x, y, costul);
//    }
//    dijkstra();
//    for ( int i = 2; i <= n; i++ )
//        if(d[i] == inf) g<<0<<" ";else g<< d[i]<<" ";
//    g<<'\n';
//
//    return 0;
//}
////Dijkstra 40p  cu memorare graf cu matrice de adiacenta
////O(n*n)clasic nu se incadreaza in timp si in memorie
//#include <fstream>
//#define inf 100000000
//using namespace std;
//ifstream f("dijkstra.in");
//ofstream g("dijkstra.out");
//int p[1500],a[1500][1500], sel[1500], d[1500], i, m, n, l, c, cost, s, nc;
//void dijkstra (int s) {
//	int min, dn, jmin, j;
//	for (i = 1; i <= n; i++)
//		{d[i]=a[s][i];if(d[i]!=inf)p[i]=s;}     // Initializam distanta fata de sursa.
//    sel[s]=1; // Aratam ca sursa este selectata.
//	d[s] = 0;   // Distanta de la sursa la sursa este 0.
//	for (i = 2; i <= n; i++) {
//		min = inf;
//		for (j=1;j<=n;j++) // pentru fiecare nod
//			if (sel[j] != 1) // daca nu este selectat
//				if (d[j]< min) {    // daca avem o valoare mai mica pentru distanta
//					min = d[j];  // actualizam min
//				jmin = j;          // retinem nodul care ne da minimul [jmin]
//				}
//      sel[jmin]=1; // Includem nodul jmin in multimea nodurilor selectate.
//		for (j=1;j<=n;j++)     // Pentru fiecare nod_
//			if (sel[j]!=1) {             // neselectat
//				dn=d[jmin]+a[jmin][j]; // Calculam distanta noua, folosind jmin.
//				if (dn < d[j])          // Daca am gasit un lant mai scurt prin jmin,
//					{d[j]=dn;p[j]=jmin;}             // actualizam distanta de la sursa la nod.
//			}
//	}
//}
//
//int main () {
//	f >> n >> m;
//	for (l = 1; l <= n; l++)
//		for (c = 1; c <= n; c++)
//			a[l][c] = inf;
//	for (i = 1; i <= m; i++) {
//		f >> l >> c; f >> a[l][c];
//	}
//	dijkstra(1);
//	for (i = 2; i <= n; i++)
//	  if(d[i] == inf) g << "0 "<<' ';
//	  else	g << d[i] << ' ';
//		g<<endl;
//
//}