#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=50000;
class Edge{
    public:
        int v,c;
        Edge(){
        }
        Edge(int vv,int cc){
            v=vv;
            c=cc;
        }
        bool operator<(const Edge&e)const{
            return e.c<c;
        }
};
vector<Edge>g[N+1];
priority_queue<Edge>h;
int dist[N+1];
int n,m;
void dijkstra(){
    int i;
    h.push(Edge(1,0));
    while(!h.empty()){
        Edge dad=h.top();
        h.pop();
        for(i=0;i<g[dad.v].size();i++){
            Edge son=g[dad.v][i];
            if(son.v!=1&&(dist[son.v]==0||dist[dad.v]+son.c<dist[son.v])){
                dist[son.v]=dist[dad.v]+son.c;
                h.push(Edge(son.v,dist[son.v]));
            }
        }
    }
}
int main(){
    int i,x,y,z;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        g[x].push_back(Edge(y,z));
    }
    dijkstra();
    for(i=2;i<=n;i++)
        printf("%d ",dist[i]);
    return 0;
}