#include<iostream>
#include<fstream>

#define inputfile "dmin.in"
#define outputfile "dmin.out"

const int NMAX = 1500;
const int INF = 0x7fff;

typedef struct rec {
  int key;
  int w;
  rec* next;
} node;

using namespace std;

void ReadData(node* G[NMAX], int &n, int &m) {
  ifstream from(inputfile);
  from>>n>>m;
  for (int i = 1; i<=n; i++) {
    G[i] = new node;
    G[i]->next = NULL;
  }
  for (int i = 1; i<=m; i++) {
    int x,y,z;
    from>>x>>y>>z;
    node* p = new node;
    p->key = y;
    p->w = z;
    p->next = G[x]->next;
    G[x]->next = p;

    p = new node;
    p->key = x;
    p->w = z;
    p->next = G[y]->next;
    G[y]->next = p;
  }
  from.close();
}

int ExtractMin(int Q[NMAX], int &heap_size) {
  int min = Q[1];
  Q[1] = Q[heap_size];
  Q[heap_size] = Q[1];
  heap_size--;
  return min;
}

void Heapify(int Q[NMAX], int heap_size, int d[NMAX], int i) {
  int l = (2 * i);
  int r = (2 * i) + 1;
  int min;
  if ( (l <= heap_size) && (d[Q[l]] < d[Q[i]]) ) min = l;
  else min = i;
  if ( (r<=heap_size) && (d[Q[r]]< d[Q[min]]) )  min = r;

  if (min != i) {
    int aux = Q[min];
    Q[min] = Q[i];
    Q[i] = aux;
    Heapify(Q,heap_size,d,min);
  }
}

void Relax(int u, int v, int w, int d[NMAX], int nr[NMAX]) {
  if (d[v] >= d[u]+w) {
    if (d[v] == d[u] + w) nr[v] +=nr[u];
    else nr[v] = nr[u];
    d[v] = d[u] + w;
  }
  // else if (d[v] = d[u] + w) 
  //  nr[v] += nr[u];
}

void Dijkstra(node* G[NMAX], int n) {
  int d[NMAX], nr[NMAX], Q[NMAX];
  for (int i = 2; i<=n; i++) { d[i] = INF; nr[i] = 0; }
  d[1] = 0; nr[1] = 1;

  for (int i = 1; i<=n; i++) Q[i] = i;
  int heap_size = n;

  while (heap_size != 0) {
    int u = ExtractMin(Q,heap_size);
    node* p = G[u]->next;
    while (p != NULL) {
      Relax(u,p->key,p->w,d,nr); 
      p = p->next;
    }
    for (int i = heap_size/2; i>=1; i--) 
      Heapify(Q,heap_size,d,i);
  }
  ofstream to(outputfile);
  for (int i = 2; i<=n; i++) to<<nr[i]<<' '; 
  to.close();
}

int main() {
  int n,m;
  node* G[NMAX];
  ReadData(G,n,m);
  Dijkstra(G,n);
}