#include<bits/stdc++.h>
#define int long long
using namespace std;
int head[5050],n,m,tot,vis[5050],dis[5050];
struct E{int next,to,d;}edge[66666];
typedef pair<int,int> P;
void add(int u,int v,int w)
{
    edge[++tot].next=head[u];
    edge[tot].to=v;
    edge[tot].d=w;
    head[u]=tot;
}
void SPFA()
{
    queue<int> q;
    q.push(1);
    vis[1]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();vis[x]=0;
        for(int i=head[x];i;i=edge[i].next)
        {
            if(dis[x]+edge[i].d<dis[edge[i].to])
            {
                dis[edge[i].to]=dis[x]+edge[i].d;
                if(!vis[edge[i].to])
                {
                    q.push(edge[i].to);
                    vis[edge[i].to]=1;
                }
            }
        }
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    SPFA();
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==0x3f3f3f3f3f3f3f3f)cout<<-1<<" ";
        else cout<<dis[i]<<" ";
    }
    return 0;
}