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

using namespace std;

const int INF = 2e9;

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

struct Node {
    int node, cost;
    bool operator<(const Node& other) const {
        return cost > other.cost;
    }
};

int n, m;
int dist[50100];
bool visited[50100];
priority_queue<Node> Q;
vector<vector<pair<int, int>>> adjList;

void dijkstra(int start)
{
    dist[start] = 0;

    for(int i = 1; i <= n; i++)
        dist[i] = INF;

    Q.push({start, 0});

    while(!Q.empty())
    {
        int vertex = Q.top().node;
        int c = Q.top().cost;
        Q.pop();

        if(visited[vertex] == 0)
        {
            visited[vertex] = 1;

            cout << vertex << ' ' << c << '\n';

            int len = adjList[vertex].size();

            for(int i = 0; i < len; i++)
            {
                int v = adjList[vertex][i].first;
                int d = adjList[vertex][i].second;

                cout << dist[v] << ' ' << d << '\n';

                if(c + d < dist[v])
                {
                    dist[v] = c + d;
                    Q.push({v, dist[v]});
                }
            }
        }
    }
}

int main()
{
    in >> n >> m;

    adjList.resize(n + 5);

    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;

        adjList[x].push_back({y, cost});
    }

    dijkstra(1);

    for(int i = 2; i <= n; i++)
    {
        if(dist[i] == INF)
            out << 0 << ' ';
        else
            out << dist[i] << ' ';
    }

    out << '\n';

    return 0;
}