#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
const int MAX=1000000000;
long long int dis[maxn];
struct edge
{
    int v,w;
};
struct node
{
    int dis,u;
    bool operator<(const node& a) const {return dis>a.dis;}
};
int h[30005];
vector<edge>e[maxn];
vector<edge>E[maxn];
long long cnt[maxn],vis[maxn];
queue<int>q;
void dijkstra(int n,int s)
{
    priority_queue<node>pq;
    dis[s]=0;
    for(int i=1;i<=n;i++)
        dis[i]=MAX;
    pq.push((node){0,s});
    while(!pq.empty())
    {
        int u=pq.top().u;
        pq.pop();
        if(vis[u])
            continue;
        vis[u]=true;
        for(int j=0;j<E[u].size();j++)
        {
            edge ed=E[u][j];
            int v=ed.v,w=ed.w;
            if(dis[v]>dis[u]+w)
                dis[v]=dis[u]+w,pq.push((node){dis[v],v});
        }
    }
    return ;
}
bool spfa(int n,int s)
{
    for(int i=1;i<=n;i++)
        h[i]=MAX,vis[i]=false;
    h[s]=0,vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop(),vis[u]=0;
        for(auto ed:e[u])
        {
            int v=ed.v,w=ed.w;
            if(h[v]>h[u]+w)
            {
                h[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n)
                    return 0;
                if(!vis[v])
                    q.push(v),vis[v]=1;
            }
        }
    }
    return 1;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[u].push_back((edge){v,w});
    }
    for(int i=1;i<=n;i++)
        e[0].push_back((edge){i,0});
    bool flag=spfa(n,0);
    if(flag==0)
    {
        cout<<"-1"<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<e[i].size();j++)
            E[i].push_back((edge){e[i][j].v,e[i][j].w+dis[i]-dis[e[i][j].v]});
    for(int i=1;i<=n;i++)
    {
        long long ans=0;
        dijkstra(n,i);
        for(int j=1;j<=n;j++)
            if(dis[j]==MAX)
                ans+=MAX;
            else
                ans+= j * (dis[j] + h[j] - h[i]);
        cout<<ans<<endl;
    }
    return 0;
}

都几乎成对着SF的代码抄了还没抄对（）