#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, i;

int main()
{

    f>>n>>m;
    vector < list < pair <int, int> > >adjacencyList(n+1);
    vector<int> dist(n+1, INF);
    set< pair<int, int> >setds;

    for(i=1; i<=m; i++){

        int x, y, z;
        f>>x>>y>>z;

        adjacencyList[x].push_back(make_pair(y, z));

    }

    setds.insert(make_pair(0, 1));
    dist[1] = 0;

    while(!setds.empty()){

        pair<int, int> tmp = *(setds.begin());
        setds.erase(setds.begin());

        int u = tmp.second;

        for(pair<int, int> aux:adjacencyList[u]){

            int v = aux.first;
            int weight = aux.second;

            if(dist[v] > dist[u] + weight){

                if(dist[v] != INF)
                    setds.erase(setds.find(make_pair(dist[v], v)));

                dist[v] = dist[u] + weight;
                setds.insert(make_pair(dist[v], v));

            }

        }

    }

    for(int i = 2; i<=n; i++)
        g<<dist[i]<<' ';

    cout<<sizeof(adjacencyList)<<'\n'<<sizeof(dist)<<'\n'<<sizeof(setds);

    return 0;
}