#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int NMAX = 50003;
const int INF = 1e9;
int dp[NMAX];
struct cmp{
    inline bool operator ()(const int A,const int B)
    {
		return dp[A] > dp[B];
    }
};
multiset < int , cmp > Q;
vector < pair < int ,int > > G[NMAX];
bool viz[NMAX];
inline void Dijkstra() {
	Q.insert(1);
    while(!Q.empty()) {
        int nod = *Q.begin();
        Q.erase(Q.begin());
        if(viz[nod] == 1)
			continue;
		viz[nod] = 1; 
		for(auto i: G[nod]) {
			int y = i.first;
			int cost = dp[nod] + i.second;
            if(dp[y] > cost) {
                Q.erase(y);
				dp[y] = cost;
				Q.insert(y);
            }
        }
    }
}
int main() {
	int n, m;
    f>> n >> m;
	while (m--) {
		int x, y , c;
        f>> x >> y >> c;
		G[x].push_back(make_pair(y,c));
    }
    for(int i = 2;i <= n;i++)
        dp[i] = INF;
    Dijkstra();
    for(int i = 2;i <= n; i++)
		g<<( dp[i] != INF? dp[i] : 0 )<<" ";
    g<<"\n";
    return 0;
}