#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <climits>
#define NMAX 50004
using namespace std;
vector<pair<int, int>> edges[NMAX];
int N, M;
unsigned int dist[NMAX];
bool comparator(pair<int, int> p1, pair<int, int> p2) {
    if (p2.second > p1.second)
      return false;
    return true;
}
void read() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d", &N, &M);
    int a, b, c;
    for (int i = 0; i < M; i++) {
        pair<int, int> p;
        scanf(%d%d%d, &a, &b, &c);
        p.first = b;
        p.second = c;
        edges[a].push_back(p);
        push_heap(edges[a].begin(), edges[a].end(), comparator);
    }
    for (int i = 2; i <= N; i++) {
        dist[i] = -1;
        dist[i] >>= 1;
    }
}
void solve() {
    queue<int> q;
    q.push(1);
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        int s = edges[x].size();
        while(s) {
            int node = edges[x].front().first;
            unsigned int cost = edges[x].front().second;
            pop_heap(&edges[x][0], &edges[x][s], comparator);
            s--;
            if (dist[x] + cost < dist[node]) {
                dist[node] = dist[x] + cost;
                q.push(node);
            }
        }
        make_heap(&edges[x][0], &edges[x][s], comparator);
    }
}
int main() {
    read();
    solve();
    int y = -1;
    y >>= 1;
    for (int i = 2; i <= N; i++) 
        printf("%d", dist[i] == y ? 0 : dist[i]);
    return 0;
}