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

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

#define INF 50005
typedef pair<int, int> iPair;
vector<iPair> G[INF];
int n, m;
void Dijkstra(int start){
        
        priority_queue<iPair, vector<iPair>, greater<iPair>> Q;
        Q.push(make_pair(0, start));
        
        vector<int> Distance(n + 1, INF);
        Distance[start] = 0;

        while(!Q.empty()){
            int node = Q.top().second;
            Q.pop();
            for(auto i:G[node]){
                int v = i.first;
                int weight = i.second;
                if(Distance[v]>Distance[node]+weight){
                    Distance[v] = Distance[node] + weight;
                    Q.push(make_pair(Distance[v], v));
                }
            }
        }
        for (int i = 2; i <= n;i++)
            if(Distance[i]!=INF)
                cout << Distance[i] << ' ';
            else
                cout << "0 ";
        exit(0);
}

void read(){
    cin >> n >> m;
    for (int x, y, w, i = 1; i <= m;++i)
        cin >> x >> y >> w,
            G[x].push_back(make_pair(y, w));
    Dijkstra(1);
}

int main(){

    read();

    return 0;
}