#include <bits/stdc++.h>
using namespace std;

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

vector<vector<pair<int,int>>> g;
int n,m;

void disjkstra(int x) {
    priority_queue<pair<int,int>> pq;
    pq.push({0,x});

    // vector<bool> f(n+1,0);
    vector<int> pos(n+1,INT_MAX);

    while(pq.size()){
        auto curr=pq.top();
        pq.pop();
        cout<<curr.second<<" d: "<<curr.first<<"\n"<<"sec : ";
        for(auto next:g[curr.second]){
            if(pos[next.second]!=INT_MAX)
                continue;

            cout<<next.second<<" ";

            pos[next.second]=curr.first-next.first;
            pq.push({pos[next.second], next.second});
        }
        cout<<"\n\n";
    }
    for(int i=2;i<pos.size();++i){
        fout<<(pos[i]==INT_MAX? 0:-pos[i])<<" ";
    }
}

int main() {
    fin>>n>>m;
    g.resize(n+1);
    for(int i=1;i<=m;++i){
        int a,b,c;
        fin>>a>>b>>c;
        g[a].push_back({c,b});
    }
    disjkstra(1);
}