#include<cstdio>
#include<queue>
#include<utility>
#define N 50000
#define MULT 2000000000
using namespace std;

class mazi{
public:
    int nod,cost;

    bool operator < (const mazi a) const{
        return (cost>a.cost);
    }

    bool operator > (const mazi a) const{
        return (cost<a.cost);
    }
};

priority_queue<mazi> heap;

vector<pair<int,int> > vecin[N+1];
bool viz[N+1];
int dist[N+1];

mazi make_mazi(int nod,int cost){
    mazi a;

    a.nod=nod;
    a.cost=cost;

    return a;
}

void dijkstra(){
    int nod=1;

    dist[nod]=0;
    heap.push(make_mazi(nod,dist[nod]));

    while(!heap.empty()){
        nod=heap.top().nod;
        heap.pop();
        viz[nod]=true;

        for(int i=0;i<vecin[nod].size();i++){
            int now=vecin[nod][i].first;
            int cost=vecin[nod][i].second;

            if (dist[now]>dist[nod]+cost){
                dist[now]=dist[nod]+cost;
                heap.push(make_mazi(now,dist[now]));
            }
        }

        while(!heap.empty() &&viz[heap.top().nod]==true) heap.pop();
    }
}

int main(){
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    int n,m,i;

    scanf ("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        int x,y,z;
        scanf ("%d%d%d",&x,&y,&z);

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

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

    dijkstra();

    for(i=2;i<=n;i++)
        printf ("%d ",(dist[i]==MULT ? 0 : dist[i]));

    return 0;
}