#include <cstdio>
#include <vector>
#include <queue>

using std::vector;
using std::queue;

#include <cstdio>

template<int SIZE>
class ReadStream {
private:
    FILE* stream;

    int pos;
    char buffer[SIZE + 1];

public:
    ReadStream(FILE* stream) {
        this->stream = stream;
        this->pos = SIZE;
    }

    int nextInt() {
        int answer = 0;
        int readSize;

        while (true) {
            if (this->pos == SIZE) {
                readSize = fread(this->buffer, sizeof(char), SIZE, this->stream);
                this->buffer[readSize] = 0;
                this->pos = 0;
            }
            if ('0' <= this->buffer[this->pos] && this->buffer[this->pos] <= '9') {
                break;
            } else {
                ++this->pos;
            }
        }
        while (true) {
            if (this->pos == SIZE) {
                readSize = fread(this->buffer, sizeof(char), SIZE, this->stream);
                this->buffer[readSize] = 0;
                this->pos = 0;
            }
            if (!('0' <= this->buffer[this->pos] && this->buffer[this->pos] <= '9')) {
                break;
            } else {
                answer *= 10;
                answer += this->buffer[this->pos] - '0';
                ++this->pos;
            }
        }

        return answer;
    }

    char nextChar() {
        int readSize;
    if (this->pos == SIZE) {
      readSize = fread(this->buffer, sizeof(char), SIZE, this->stream);
      this->buffer[readSize] = 0;
      this->pos = 0;
    }
    return this->buffer[this->pos++];
    }
};

const int MAX_N = 50000;

struct Muchie {
  int nod;
  int cost;
};

int V, E;
vector<Muchie> vecini[1 + MAX_N];

queue<int> coadaBF;
bool inCoadaBF[1 + MAX_N];

int distanta[1 + MAX_N];


int main(void) {
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  ReadStream<1000000> read(stdin);
  int i;

  // citirea datelor
  //scanf("%d %d", &V, &E);
  V = read.nextInt();
  E = read.nextInt();
  printf("%d %d\n", V, E);
  for (i = 0; i < E; ++i) {
    int u, v, c;
    //scanf("%d %d %d", &u, &v, &c);
    u = read.nextInt();
    v = read.nextInt();
    c = read.nextInt();
    vecini[u].push_back({v, c});
  }

  // calcularea solutiei
  int sursa = 1;
  coadaBF.push(sursa);
  inCoadaBF[sursa] = true;
  for (i = 1; i <= V; i++) {
    distanta[i] = 0x3fffffff;
  }
  distanta[sursa] = 0;

  while (!coadaBF.empty()) {
    int nod = coadaBF.front();
    coadaBF.pop();
    inCoadaBF[nod] = false;
    //for (i = 0; i < vecini[nod].size(); i++) {
    //  Muchie muchie = vecini[nod][i];
    for (Muchie muchie : vecini[nod]) {
      if (distanta[muchie.nod] > distanta[nod] + muchie.cost) {
        distanta[muchie.nod] = distanta[nod] + muchie.cost;
        if (!inCoadaBF[muchie.nod]) {
          coadaBF.push(muchie.nod);
          inCoadaBF[muchie.nod] = true;
        }
      }
    }
  }

  // afisarea solutiei
  for (i = 2; i <= V; i++) {
    if (distanta[i] == 0x3fffffff) {
      distanta[i] = 0;
    }
    printf("%d ", distanta[i]);
  }
  printf("\n");

  return 0;
}