#include <queue>
#include <vector>
#include <cstdio>
using namespace std;

typedef pair<int,int> ii;
#define INF ~(1<<31)
#define fi first
#define se second

const int NMAX = 50000;
int N,M,d[NMAX];
vector <ii> G[NMAX];

void readGraph() {   

     freopen("dijkstra.in","r",stdin);  
     scanf("%d%d",&N,&M);
     
     for(int x,y,w,i=0;i<M;++i) {
                        
             scanf("%d%d%d",&x,&y,&w);
             G[--x].push_back(make_pair(--y,w));
             }
     }

struct comp {
       
       bool operator()(const ii &a,const ii &b) {
            return a.se > b.se ? 1 : a.se == b.se ? a.fi > b.fi : 0;
       }
};

void dijkstra() {
     
     priority_queue < ii, vector<ii>, comp> Q;
     
     for(int i = 0 ; i < N; ++i)
      d[i] = INF;
     
     d[0] = 0; Q.push( make_pair(0,0) );
     
     for(ii min; !Q.empty() ; ) {
                                            
               min = Q.top();
               Q.pop();
               printf("%d %d\n",min.fi,min.se);
               if(d[min.fi] == min.se)  
               for(vector<ii>::iterator p = G[min.fi].begin(); p != G[min.fi].end(); ++p)
               if(d[min.fi] + p->se < d[p->fi]) 
                            
                            Q.push( make_pair(p->fi, d[p->fi] = d[min.fi] + p->se ) );                                                                  
     } 
}

void writeDist() {
        
     freopen("dijkstra.out","w",stdout);
     for(int i=1;i<N;++i)
             printf("%d ",d[i]==INF?0:d[i]);
     }   

int main() {    
    readGraph();
    dijkstra();
    writeDist();
}