#include <fstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int INF=9999;
int       n;
int       muchii;
int       v[10000][10000];

int       Dist[10000];
bool      Viz[10000];

inline int MIN(int a, int b) { return a<b?a:b; }

void Dijkstra(int nod);
void citire();
void debug();
int main()
{
  citire();
  for(int i=1; i<=n; i++)
  {
    Dist[i]=INF;
    Viz[i]=false;
  }
  Dist[1]=0;

  Dijkstra(1);
 // debug();
 /* cin.sync();
  cin.get();*/

  FILE *g=fopen("dijkstra.out","w");
  for(int i=2; i<=n; i++)
    fprintf(g,"%d ",Dist[i]);

  fclose(g);

  return 0;
}

void Dijkstra(int nod)
{
   Viz[nod]=true;
   for(int i=1; i<=n; i++)
    if(v[nod][i])
      Dist[i]=MIN(Dist[nod]+v[nod][i],Dist[i]);

   //caut
   int min=INF,
       minpoz=0;

  for(int i=1; i<=n; i++)
    if(Viz[i]==false && Dist[i]<min)
    {
      min=Dist[i];
      minpoz=i;
    }
  if(minpoz!=0)
    Dijkstra(minpoz);
}

void debug()
{
  cout<<"\nDist: ";
  for(int i=1; i<=n; i++)
    cout<<Dist[i]<<" ";

  cout<<"\nViz:  ";
  for(int i=1; i<=n; i++)
    cout<<Viz[i]<<" ";
}

void citire()
{
  FILE *f=fopen("dijkstra.in","r");
  fscanf(f,"%d %d",&n,&muchii);

  for(int i=1; i<=muchii; i++)
  {
    int a,b,cost;
    fscanf(f,"%d %d %d",&a,&b,&cost);
    v[a][b]=cost;
  }

  for(int i=1; i<=n; i++)
  {
    cout<<endl;
    for(int j=1; j<=n; j++)
      cout<<v[i][j]<<" ";
  }
  fclose(f);
}