#include<iostream>
#include<fstream>
#include<vector>


using namespace std;

const int inf = (1<<31)-1;

struct Nod{
    int nod;
    int cost;
    Nod* next {nullptr};


    Nod* create(int nod, int cost){
        Nod* newNode = new Nod();
        newNode->nod = nod;
        newNode->cost = cost;
        newNode->next = {nullptr};

        return newNode;
    };

    void push(Nod *&top, int nod, int cost){
        Nod* newNode = create(nod, cost);
        newNode->next = top;
        top = newNode;
    };

    void pop(Nod *&top, int nod){
        Nod* tmp = top;
        Nod* prev = nullptr;

        if(top->nod == nod){
            top = top->next;
            delete tmp;
            return;
        }

        while(tmp != nullptr){
            if(tmp->nod == nod){
                prev->next = tmp->next;
                delete tmp;
                return;
            }

            prev = tmp;
            tmp = tmp->next;
        }
    }

    int nextDij(Nod *top){
        Nod* tmp = top;
        Nod* res = top;
        int costMin = inf;
        
        while(tmp != nullptr){
            if(tmp->cost < costMin){
                res = tmp;
                costMin = tmp->cost;
            }

            tmp = tmp->next;
        }

        if(costMin < inf){
            return res->nod;
        } else {
            return inf;
        }
    }

    bool isEmpty(Nod *top){
        return top == nullptr;
    }
};

void dij(int nodStart, vector<int> &d, vector<vector<pair<int,int>>> g, vector<bool> &visited){
    d[nodStart] = 0;
    Nod* top = new Nod;
    top->nod = nodStart;
    top->cost = 0;

    visited[nodStart] = true;

    while(!top->isEmpty(top)){
        int nodCurent = top->nextDij(top);
        if(nodCurent == inf) return;
        top->pop(top, nodCurent);

        for(unsigned int i = 0; i<g[nodCurent].size(); i++){
            int vecin = g[nodCurent][i].first;
            int cost = g[nodCurent][i].second;

            // Relaxare
            if(d[nodCurent] + cost < d[vecin]){
                d[vecin] = d[nodCurent] + cost;

                if(visited[vecin] == false){
                    top->push(top, vecin, d[vecin]);
                    visited[vecin] = true;
                }
            }
        }
    }
}

int main(){
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int n, m;
    fin>>n>>m;

    vector<vector<pair<int,int>>>g(n+1);

    for(int i = 0; i<m;i++){
        int x, y, c;
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }

    vector<int> d(n+1);
    for(int i = 1; i< d.size(); i++){
        d[i] = inf;
    }
    vector<bool> visited(n+1);
    int nodStart = 1;

    dij(nodStart, d, g, visited);

    for(int i = 1; i<=n;i++){
        if(i == nodStart) continue;

        fout<<d[i];
    }


    return 0;
}