#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e6 + 10;
const long long inf = 1e14;
vector<pair<long long, long long>> ve[maxn];
long long dis[maxn];
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
               greater<pair<long long, long long>>>
    heap;
int N, M;
void init() {
  for (int i = 1; i <= N; i++) dis[i] = inf;
  for (int i = 1; i <= N; i++) ve[i].push_back({0, i - 1});
}
long long Dji() {
  heap.push({0, 1});
  dis[1] = 0;
  while (heap.size()) {
    auto cur = heap.top();
    heap.pop();
    cout << cur.first << cur.second << "\n";
    long long d = cur.first, id = cur.second;
    for (auto v : ve[id]) {
      long long w = v.first, id2 = v.second;
      cout << v.first << v.second << "\n";
      if (d + w < dis[id2]) {
        dis[id2] = d + w;
        heap.push({dis[id2], id2});
      }
    }
  }
  if (dis[N] == inf) return -1;
  return dis[N];
}
int main() {
  cin >> N >> M;
  init();
  int a, b, c;
  for (int i = 0; i < M; i++) {
    scanf("%d%d%d", &a, &b, &c);
    ve[a].push_back({c, b});
  }
  cout << Dji() << endl;
  return 0;
}
