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

struct muchie {
    int nod,dist;
};

struct comp {
    bool operator()(muchie &a,muchie &b) {
        return a.dist>b.dist;
    }
};

priority_queue <muchie,vector<muchie>,comp> q;
vector <muchie> v[50005];
unsigned int dist[50005];
int n,m;
bool viz[50005];
muchie mk_muchie(int nod,int dist) {
    muchie nou;
    nou.nod = nod;
    nou.dist = dist;
    return nou;
}

int main() {
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=2;i<=n;i++) dist[i] = 0xffffffff;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
                int t,f,c;
                scanf("%d %d %d",&t,&f,&c);
                v[t].push_back(mk_muchie(f,c));
        }
    }
    q.push(mk_muchie(1,0));
    while (!q.empty()) {
        muchie n = q.top(); q.pop();
        viz[n.nod]=true;
        while (!v[n.nod].empty()){
                muchie nou = v[n.nod].back(); v[n.nod].pop_back();
                int nod = nou.nod, dst = nou.dist;
                if (dist[nod] > n.dist + dst && !viz[nod]) {
                    dist[nod] = n.dist + dst;
                    q.push(mk_muchie(nod,dist[nod]));
                }
        }
    }
    for (int i=2;i<=n;i++) {
        if (dist[i] != 0xffffffff) printf("%d ",dist[i]);
        else printf("0 ");
    }
    return 0;
}