#include <iostream>
#include <fstream>
#include <queue>
#include <list>
#define INF 1200
#define NN 50002
using namespace std;

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

priority_queue <pair <int, int> > h;
int d[NN],n,m;
bool s[NN];

struct graph{
    list <int> cos;
    list <int> ver;
}G[NN];

void read (){
    in>>n>>m;
    int x,y,c;
    for(int i=1;i<=m;i++){
        in>>x>>y>>c;
        G[x].ver.push_back(y);
        G[x].cos.push_back(c);
    }
}

void af(){
    for(int i=1;i<=n;i++){
        list<int>::iterator it=G[i].ver.begin();
        for(;it!=G[i].ver.end();++it){
            cout<<*it<<' ';
        }
        cout<<endl;
    }
}

void djik (int x){
    int i, y, c;
    for(i=1; i<=n;i++){
        d[i]=INF;
        s[i]=false;

    }
    d[x]=0;
    h.push(make_pair(0,x));
    while(!h.empty()){
        while(!h.empty()&&s[h.top().second])
            h.pop();
        if(h.empty())break;
        x=h.top().second;
        h.pop();s[x]=true;
        int so=G[x].ver.size();
        for(i=1;i<=so;i++){
            //cout<<x<<' ';
            y=G[x].ver.front(); //cout<<y<<' ';
            G[x].ver.pop_front();
            c=G[x].cos.front(); //cout<<c<<endl;
            G[x].cos.pop_front();
            if(d[x]+c<d[y]){
                d[y]=d[x]+c;
                h.push(make_pair((-1)*d[y],y));
            }
        }
    }
}

void afij (){
    for(int i=2;i<=n;i++)
        out<<d[i]<<' ';
}

int main()
{
    read();
    djik(1);
    afij();

    return 0;
}