using namespace std;
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

#define maxn 50001
#define oo 0x3f3f3f3f
#define pb push_back
#define mk make_pair

int d[maxn], n, m;

struct cmp{
    bool operator()(const int &a, const int &b)const
    {
            if(d[a]>d[b]) return 1;
            return 0;
    }
};

vector<pair<int, int> > a[50001];

void dijkstra()
{
    priority_queue<int, vector<int>, cmp>Q;
    Q.push(1);
    memset(d, oo, sizeof(d));
    d[1]=0;
    int u, i;
    while(!Q.empty())
    {
            u = Q.top();
            Q.pop();
 
            for(i = 0; i < a[u].size() ; ++i)
                if(d[u] + a[u][i].second < d[a[u][i].first])
                {
                        d[a[u][i].first] = d[u] + a[u][i].second;
                        Q.push(a[u][i].first);
                        
                }
    }
    for(i = 1; i <= n; ++i) if(d[i] == oo) d[i] = 0;
    freopen("dijkstra.out","w",stdout);
    for(i = 2; i <= n; ++i)printf("%d ", d[i]);
    printf("\n");
}
int main()
{
	int i, x, y, cost;
	freopen("dijkstra.in", "r", stdin);
	scanf("%d%d", &n, &m);
	for(i = 1; i <= m; ++i) {
		scanf("%d%d%d", &x, &y, &cost);
		a[x].push_back(mk(y, cost));
	}
    dijkstra();
    return 0;
}