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

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

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

class g{
    int Node;
    vector<iPair> *G;
public:
    g(int n){
        Node = n + 1;
        G = new vector<iPair>[Node];
    }
    void add_edge(int x,int y,int w){
        G[x].push_back(make_pair(y, w));
    }

    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;
            if(Q.top().first>Distance[Node]){
                Q.pop();
                continue;
            }
            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;
}