#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define nmax 50020
#define inf 0x3f3f3f3f

using namespace std;

int n,m;
int dist[nmax];
vector < pair<int,int> > graph[nmax];
priority_queue <pair<int,int> > heap;

void read(){
    scanf("%d %d ",&n,&m);
    int x,y,z;
    while(m--){
        scanf("%d %d %d ",&x,&y,&z);
        graph[x].push_back(make_pair(z,y));
    }
}

void dijkstra(){
    memset(dist,inf,sizeof(dist));
    dist[1] = 0;
    int x,cost;
    heap.push(make_pair(0,1));
    while(!heap.empty()){
        x = heap.top().second;
        heap.pop();
        for(vector <pair<int,int> > :: iterator it = graph[x].begin() ; it != graph[x].end() ;++it){
            if(dist[it->second] > dist[x] + it->first){
                dist[it->second] = dist[x] + it->first;
                heap.push(make_pair(-dist[it->second],it->second));
            }
        }
    }
}

void print(){
    for(int i = 2 ; i <= n; i++){
        if(dist[i] != inf)printf("%d ",dist[i]);
        else printf("0 ");
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    read();
    dijkstra();
    print();

    return 0;
}