#include<cstdio>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;

struct Edge{///we use a struct for the code to be easier to read
    int to,weight;
};

vector<Edge> gr[100000];///will be used for an adj. list
int n,m,used[100000],dist[100000];

///make an adj. list
void init(){
    int from,to,weight;

    scanf("%d %d",&n,&m);

    for(int i=0;i<m;i++){
        scanf("%d %d %d",&from,&to,&weight);

        gr[from].push_back({to,weight});
        gr[to].push_back({from,weight});
    }
}

void dijkstra(int start){
    ///priorirt queue with inversed priority. We will store pairs of elements where the first is the distance to the node and the second is the node
    ///we need only the node in the code below but the distance is needed for the sorting part. The priority is inversed so that the first node is the one with the lowest dist
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > nodes;
    int node;

    ///initializing stuff for the algorithm. All nodes are unused, distances to all are inf, distance to the start is 0 and we add it to the queue
    fill(used,used+n,0);
    fill(dist,dist+n,INT_MAX/10);
    dist[start]=0;
    nodes.push({0,start});

    while(!nodes.empty()){
        node=nodes.top().second;///take the first node and remove it
        nodes.pop();

        if(used[node])continue;///if it is used it means we get it a second time from the queue so we just discard it and do nothing

        used[node]=1;///mark the node as used after we got it out of the queue

        for(int i=0;i<gr[node].size();i++){///for each of its neighbors
            Edge temp = gr[node][i];

            if(used[temp.to])continue;///if the neighbor is already used we have found the optimal distance to it, so we do nothing

            if(dist[temp.to] > dist[node] + temp.weight){///else if the distance we previously found to it is greater then the distance to the current node + the edge
                dist[temp.to] = dist[node] + temp.weight;///we update the distance since we have found a better path
                nodes.push({dist[temp.to],temp.to});///add it to the queue
            }
        }
    }

    ///here the algorithm has ended and dist[i] is the minimal distance from the start node to node i
    ///Note that if there are components that are unreachable from the starting node the distance to them will be INT_MAX/10 (the distance we used in the initialization)
}

void print(){
    for(int i=0;i<n;i++){
        printf("dist to %d is %d\n",i,dist[i]);
    }
}

int main(){
    init();
    dijkstra(3);
    print();
}

/**
6 8
0 2 2
0 4 0
0 5 2
1 4 4
1 4 7
2 3 2
2 4 3
4 5 1
*/