#include <cstdio>
#include <vector>
#include <set>
#define MAX 50005
#define INF 0xfffff
using namespace std;

vector< pair<int,int> >U[MAX];
set< pair<int,int> >S;
int C[MAX],n;

void dijkstra(){
    int x,y,cost;
    for(int i=2;i<=n;i++)C[i]=INF;

    S.insert(make_pair(0,1));
    while(S.size()>0)
    {
        cost=S.begin()->first;
        x=S.begin()->second;
        for(int i=0;i<U[x].size();i++)
        {
            y=U[x][i].first;
            if(C[y]>cost+U[x][i].second)
            {
                C[y]=cost+U[x][i].second;
                S.insert(make_pair(C[y],y));
            }
        }
        S.erase(S.begin());
    }

}

int main(){
    int x,y,c,m;
    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",&x,&y,&c);
            U[x].push_back(make_pair(y,c));
        }
    dijkstra();
        for(int i=2;i<=n;i++)printf("%d ",C[i]);
}