#include <queue>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
inline long long read(){
    long long 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(long long 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(long long 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(long long 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(long long i=1; i<=m; ++i) {
        long long u,v,w;
        u=read();
        a[u].push_back((node) {
            read(),read()
        });
    }
    dijie(1);
    for(long long i=1; i<=n; ++i) {
        if(dis[i]==0x3f3f3f3f3f3f3f3f)
            write(-1),printf(" ");
        else
            write(dis[i]),printf(" ");
    }
    return 0;
}