#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dbz.in");
ofstream g("dbz.out");
int n,m;
struct pct
{
    int x,cost;
};
struct cir
{
    int x,y,cost;
}b[30006];
const int N=1505;
vector<pct>a[N];
int d[N],tt[N];
struct cmp
{
    bool operator()(const pct & X,const pct &Y)
    {
        return X.cost>Y.cost;
    }
};
void dijkstra(int start)
{
    priority_queue<pct,vector<pct>,cmp>q;
    q.push({start,0});
    tt[start]=start;
    d[start]=0;
    while(!q.empty())
    {
        pct nod=q.top();
        q.pop();
        if(nod.cost!=d[nod.x])
            continue;
        for(auto x : a[nod.x])
        {
            int vecin=x.x;
            int C=x.cost;
            if(d[x.x]>nod.cost+x.cost)
            {
                d[x.x]=nod.cost+x.cost;
                q.push({x.x,d[x.x]});
                if(nod.x==start)
                    tt[x.x]=x.x;
                else
                    tt[x.x]=tt[nod.x];
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int X,Y,Z;
        f>>X>>Y>>Z;
        b[i]={X,Y,Z};
        a[X].push_back({Y,Z});
        a[Y].push_back({X,Z});
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            d[j]=1e9,tt[j]=-1;
        dijkstra(i);
      //  for(int j=1;j<=n;j++)
        //    g<<d[j]<<" "<<tt[j]<<'\n';
        int mn=1e9;
        for(int j=1;j<=m;j++)
        {
            int x=b[j].x;
            int y=b[j].y;
            int cst=b[j].cost;
            if(x==i&&tt[y]!=y)
                mn=min(mn,cst+d[y]);
            else
            if(y==i&&tt[x]!=x)
                mn=min(mn,cst+d[x]);
            else
            if(tt[x]!=tt[y]&&x!=i&&y!=i)
                mn=min(mn,cst+d[x]+d[y]);
        }
        if(mn==1e9)
            g<<-1<<' ';
        else
            g<<mn<<' ';
    }
    return 0;
}