#include <iostream>
#include <fstream>

using namespace std;

const int INF = 2000000000;

int A[105][105], N, M;
int D[105], folosit[105];

void citire()
{
    ifstream f("date.in");
    f >> N >> M;
    for(int i = 1; i <= N; i ++)
    {
        for(int j = 1; j <= N; j ++)
        {
            if(i != j)
            {
                A[i][j] = INF;
            }
        }
    }
    for(int i = 1; i <= M; i ++)
    {
        int x, y, z;
        f >> x >> y >> z;
        A[x][y] = z;
        A[y][x] = z;
    }
    f.close();
}

void afisare()
{
    for(int i = 1; i <= N; i ++)
    {
        for(int j = 1; j <= N; j ++)
        {
            if(A[i][j] == INF)
            {
                cout << "-" << " ";
            }
            else
            {
                cout << A[i][j] << " ";
            }
        }
        cout << "\n";
    }
    cout << "\n";
}

void dijkstra(int k)
{
   for(int i = 1; i <= N; i ++)
   {
      folosit[i] = 0;
      D[i] = INF;
   }
   D[k] = 0;
   int nodMin, Min;
   for(int i = 0; i < N; i ++)
   {
      Min = INF;
      for(int j = 1; j <= N; j ++)
      {
         if((folosit[j] == 0) && (D[j] < Min))
         {
            nodMin = j;
            Min = D[i];
         }
      }
      folosit[nodMin] = 1;
      for(int j = 1; j <= N; j ++)
      {
         if((folosit[j]==0) && (A[j][nodMin]!=INF) && (D[nodMin] != INF) && (D[j]>D[nodMin]+A[j][nodMin]))
         {
            D[j] = D[nodMin]+A[j][nodMin];
         }
      }
   }
}

void afisareDistante()
{
   for(int i = 1; i <= N; i ++)
   {
      cout << D[i] << " ";
   }
}

int main()
{
    citire();
    afisare();
    dijkstra(1);
    afisareDistante();
    return 0;
}