#include<fstream>
#include<queue>
#define DN 50001
#include<vector>
#include<iostream>>
#define inf 0x3f3f3f3f

using namespace std;
int n,m;
int dist[DN];
vector< pair<int,int> > lst[DN];
queue<int> q;
void read()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
    for(int i=0; i<m; i++)
    {
        int a,b,c;
        f>>a;
        f>>b;
        f>>c;
        lst[a].push_back(make_pair(b,c));
    }
}

void init(){

    dist[1]=0;
    for(int i=2;i<DN;i++)
        dist[i]=inf;
    //cout<<dist[2];
}


void solve(){
    init();
    q.push(1);
    while(q.size()!=0){

        int nod=q.front();
        q.pop();
        for(int i=0;i<lst[nod].size();i++)
            {
                int next_nod=lst[nod][i].first;
                int cost=lst[nod][i].second;
                if(dist[nod]+cost<dist[next_nod])
                    {
                        dist[next_nod]=dist[nod]+cost;
                        q.push(next_nod);
                    }
            }
    }
    ofstream g("dijkstra.out");
    for(int i=2;i<=n;i++)
        g<<dist[i]<<" ";


}

int main()
{
    read();
    solve();


}