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

struct much{int b,c;};
much str;
vector<much>v[50001];
bool viz[50001];
struct cmp{
    bool operator()(const much A,const much B){
        return A.c>B.c;
    }
};
priority_queue<much,vector<much>,cmp>Q;

int n,m,a,b,c,d[50001];
int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        str.b=b;str.c=c;
        v[a].push_back(str);
    }
    for(int i=0;i<=n;i++)
        d[i]=-1;
    for(int i=0;i<v[1].size();i++){
        Q.push(v[1][i]);
        d[v[1][i].b]=v[1][i].c;
    }
    for(int i=2;i<=n;i++){
        much ales;
        ales=Q.top();
        Q.pop();
        viz[ales.b]=true;
        for(int j=0;j<v[ales.b].size();j++){
            if(viz[v[ales.b][j].b]==false)
            if(d[v[ales.b][j].b]>d[ales.b]+v[ales.b][j].c||d[v[ales.b][j].b]==-1){
                d[v[ales.b][j].b]=d[ales.b]+v[ales.b][j].c;
                str.b=v[ales.b][j].b;
                str.c=d[v[ales.b][j].b];
                Q.push(str);
            }
        }
    }

    for(int i=2;i<=n;i++)
        printf("%d ",d[i]);
    return 0;
}