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

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

#define INF 0x3f3f3f3f
typedef pair<int, int> iPair;

int n, m;

class g{
    vector<iPair> *G;
    int Nodes;
public:
    g(int n){
        Nodes=n+1;
        G = new vector<iPair>[Nodes];
    }
    void add_edge(int x,int y,int w){
        G[x].push_back(make_pair(y, w));
    }
    vector<iPair>Adj(int x){
        return G[x];
    }
    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 << ' ';
    }
};

void read(){
    cin >> n >> m;
    g Graph(n);
    for (int x, y, w, i = 1; i <= m;++i)
        cin >> x >> y >> w,
        Graph.add_edge(x, y, w);
    Graph.Dijkstra(1);
}

int main(){

    read();

    return 0;
}