#include<cstdio>
#include<vector>
#include<set>
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];
multiset<Edge>s;
int dist[N+1];
bool vis[N+1];
int n,m;
void dijkstra(){
    int i;
    s.insert(Edge(1,0));
    while(!s.empty()){
        Edge dad=*s.begin();
        s.erase(s.begin());
        for(i=0;i<g[dad.v].size();i++){
            Edge son=g[dad.v][i];
            if(son.v!=1&&(!vis[son.v]||dist[dad.v]+son.c<dist[son.v])){
                set<Edge>::iterator it=s.find(Edge(son.v,dist[son.v]));
                if(vis[son.v])
                    s.erase(it);
                dist[son.v]=dist[dad.v]+son.c;
                s.insert(Edge(son.v,dist[son.v]));
                vis[son.v]=true;
            }
        }
    }
}
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;
}