#include <queue>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    if(x<0){
    	putchar('-');
		x=-x;
	}
    if(x>9) 
		write(x/10);
    putchar(x%10+'0');
}
struct node {
	long long id,p;
	bool operator <(const node &a) const {
		return p>a.p;
	}
};
priority_queue<node> q;
vector<node> a[300007];
long long n,m,s,dis[300007],vis[300007];
void dijie(int k) {
	memset(dis,0x3f,sizeof(dis));
	dis[k]=0;
	//vis[k]=1;
	q.push((node) {
		k,0
	});
	while(!q.empty()) {
		node o=q.top();
		q.pop();
		if(vis[o.id])
			continue;
		vis[o.id]=1;
		for(int i=0; i<a[o.id].size(); ++i) {
			node l=a[o.id][i];
			if(vis[l.id]==0&&dis[l.id]>dis[o.id]+l.p) {
				dis[l.id]=dis[o.id]+l.p;
				q.push((node) {
					l.id,dis[l.id]
				});
			}
		}
	}
}
int main() {
	n=read();
	m=read();
	for(int i=1; i<=m; ++i) {
		int u,v,w;
		u=read();
		a[u].push_back((node) {
			read(),read()
		});
	}
	dijie(1);
	for(int i=1; i<=n; ++i) {
		if(dis[i]==0x3f3f3f3f3f3f3f3f)
			write(-1),printf(" ");
		else
			write(dis[i]),printf(" ");
	}
	return 0;
}