////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;

}